Нужна как можно более эффективная программа, делающая
следующее

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
никак не пойдет. Но я думаю, что расширить
пример будет не очень сложно?

<skiped>

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 „4) Пункты 2-3 повторяют, пока не будет число =1 “

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
Код примерно такой из этой статьи :

     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⁴⁰, все они приходят к 1 . Статья датирована - март 1984 г.

blueboar
Если проверять числа по порядку (по возростанию), то можно проверять только нечетные.

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 это просто:

	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Кб, не пугайтесь!