Нужна как можно более эффективная программа, делающая следующее 1) Берущая число(положительное натуральное) 2) Если четное, делит на 2 3) Если нечетное, умножает на 3 и прибавляет 1 (можно еще поделить на 2, т.к. получится четное) 4) Пункты 2-3 повторяют, пока не будет число =1 Еще не доказано, что всегда так будет, так что нужно предусмотреть вариант зацикливания И еще. Нужны большие числа. Типа 10^20 или даже больше. Так что DWORD'ом тут не обойтись. Сам я пытался написать такую программу, но по скорости она явно была не лучшая.
С 32-х битными числами можно сделать примерно так: mov eax,[number] cyc: test al,1 jnz odd shr eax,1 jmp cyc odd: mov ebx,eax shr eax,1 add eax,ebx inc eax jmp cyc ... number: dd 12345678h Вроде так если я нигде не ошибся. А в связи с чем, кстати, у тебя возникла такая задача?
Это, конечно, хорошо, но интересуют в первую очередь 128-битные числа. Задача эта возникла не у меня. Она существует уже давно и называется Collatz Problem. За доказательство, что любое число сходится подобным образом обещано 1000 фунтов стерлингов (наверное теперь уже Евро). А пока люди считают таким образом как можно большие числа (вдруг какое-нибудь не сойдется, тогда будет док-во от противного). Уже до 10^16 степени досчитали. Так что DWORD никак не пойдет. Но я думаю, что расширить пример будет не очень сложно?
blueboar Задача эта возникла не у меня. Она существует уже давно и называется Collatz Problem. Заинтриговал ты меня Но я начал не программу писАть, а ручку с листочком взял. Предлагаю на это посмотреть вот с какой стороны: - числа представляем в двоичной системе - деление на степень двойки определяется количеством нулей в конце числа (соответственно, деление на степень 2 - удалением лишних нулей Рассмотрим только последние 3 бита (нечетных чисел): 001 (*3+1) 100 011 (*3+1) 1010 -> 101 (*3+1) 10000 101 (*3+1) 10000 111 (*3+1) 10110 -> 1011 (*3+1) 10001 (*3+1) 110100 -> 1101 (*3+1) 101000 -> 101 (*3+1) 10000 001 - 1 преобразование и 2 нуля 011 - 2 преобразования и 5 нулей 101 - 1 преобразование и 4 нуля 111 - 5 преобразований и 10 нулей Одно преобразование (X*3+1)/2 может увеличить число максимум в полтора раза или 1.5 бита. Смотрим на наши тройки чисел - число изменяется на следующее кол-во бит (преобразование * 1.5 - кол-во нулей)..... везде отрицательная величина... можно предположить, что все числа сходятся..... да ты в добавок еще и проверил 10^16 штук Для затравки смотри аттач, там 4 бита. PS. Весь выше приведенный бред на математическую точность не претендует, но мне кажется нужно искать 1000 евро где-нибудь в другом месте 539929080__3x+1.zip
blueboar 2/2=1 . Кажеться тут проблема гораздо глубже ? http://www.ega-math.narod.ru/Nquant/Collatz.htm Icebp Там получаеться условие такое : IF N MOD 2 = 0 THEN N = N/2 ELSE N = 3*N + 1 Код примерно такой из этой статьи : Код (Text): mov eax,number (N) @@: mov ebx,eax shr eax,1 ; jz exit ; пришли к 4,2,1 jnc @B mov eax,ebx add eax,ebx add eax,ebx inc eax jmp @B Исследованы числа до 2<sup>40</sup>, все они приходят к 1 . Статья датирована - март 1984 г.
blueboar Тебе пойдет вариант с использованием SSE2? Если пойдет, то например деление на 2 для 128-битных чисел можно сделать так: movaps xmm0,[number] psrldq xmm0,1 movaps xmm1,[mask] pand xmm0,xmm1 movaps [number],xmm0 ... align 16 number: dq 123456789abcdefh, 521397caeh mask: dd 0ffffffffh,0ffffffffh,0ffffffffh,7fffffffh Если то число, что мы делим на 2 будет четным, то 3-ей и 4-ой строчек не надо. То есть не нужны: movaps xmm1,[mask] и pand xmm0,xmm1.
blueboar Оказывается я был неправ: инструкция PSRLDQ сдвигает содержимое XMM вправо не на число бит, указанных во втором операнде, а на число БАЙТ, указанных во втором операнде. Сам убедился в этом когда пытался написать программу, аналогичную вышеприведенной. Она у меня не работала. Когда разбирался в чем дело, то в отладчике увидел что к чему. Потом внимательно глянул в описание этой инсрукции и убедился, что именно байт, а не бит. В аттачменте программа, которая проверяет числа по твоему алгоритму. Как ей пользоваться объяснять наверное не буду, так как из текста программы наверное все будет понятно. _1380416443__TOONE.ASM
Замечания по реализации. Во-первых, незачем "в лоб" вычислять 3x+1, т.к. это число всегда четное. "Изящнее" будет сразу (3x+1)/2 = x + (x div 2) + 1. Для dword это просто: Код (Text): mov ebx,eax shr eax,1 jnc @@even ;четное adc eax,ebx ;одна инструкция вместо 4 Это же относится к MMX-реализации Icebp - не нужны будут переменная temp и цикл increm. Плюс экономия одного бесполезного цикла (т.к. 3х+1 - всегда четное). Плюс экономия кода, т.к. сложное деление мымыксов на 2 не нужно будет дублировать для чет\нечет. Во-вторых, не нужно крутить цикл до достижения единицы. Если известно, что все числа x < 2^n сходятся, то нужно выходить из цикла, если старшые разряды числа от n до Nmax равны нулю. Вообще, в этой задачке гораздо бОльшую экономию можно достичь за счет отсечения чисел, которые заведомо сходятся. Приведенная bogrus ссылочка на статью вызывает "удручающую смесь закономерности и беспорядка", якобы числа "не имеют никаких явных общих черт". Может они в десятичном виде не имеют общих черт, а в двоичном все нагляднее ? Считаем, что все x < 2^n сходятся и => все четные < 2^(n+1) тоже сходятся. Если посмотреть как работает алгоритм на младших разрядах, то увидим что, например, безусловно сходятся все числа оканчивающиеся на x101, т.к.на первом же шаге получаем несколько младших нулей и после shr получаем x < 2^n => нет смысла перебирать все старшие разряды. Числа заканчивающиеся на x001 точно сходятся если нет переноса в старший разряд (т.е. старшие 100х). Можно рассмотреть большее число разрядов и учесть "сваливание" на втором, третьем и т.д. шагах. Например, явно сходится х00011 и вообще все Х00..011..1, где нулей на 1 больше, чем единиц (сначала рост, затем спад). Вопрос как это все учесть в программе. Один из вариантов - заранее просчитать и составить табличку младших байтов, которые имеет смысл проверять (а может и вордов, если их не очень много).
В общем, отвечаю всем по-порядку. 1) У меня пень-MMX, так что никаких SSE2, MMX - можно. 2) Я написал прогу, которая считает эти числа на АСМЕ, есс-но Выложу вместе с алгоритмом на http://www.bigblueboar.narod.ru/prog.rar (ссылка прямая, на сайте на нее не указано) Нужно: 1) Указать на пути оптимизации проги (пусть даже на 2-3 такта каждый 1000 цикл) 2) Указать на пути оптимизации алгоритма (в архиве есть также алгоритм работы программы) P.S 1)Программа ищет классы - то есть минимальные числа, которые раскладываются за N шагов. Пока найдены все классы до N=2000. 2) Программа создана методом "Махохизма для Дзенствующих", как было сказано в какой-то статье, т.е. был взят Блокнот и программа "Воткнута" внутрь него прямо в машинном коде. Так что она не занимает 50Кб, не пугайтесь!
