Оптимизация программы(Гипотеза Коллатца)

@Aliaxandr · Регистрация: 03.07.2015

Author24 — интернет-сервис помощи студентам

(https://ru.wikipedia.org/Гипотеза_Коллатца)
Суть гипотезы загключается в следующем: берём целое число, если оно чётное делим его на 2, если не четное, то умножаем на 3 и добавляем единицу и так до того момента пока, число не будет равняться 1, вопрос гипотезы таков, любое ли число исходя из предыдущего алогоритма дойдет до 1.

Приведу пример для n=3;
3=3,10,5,16,8,4,2,1. Т.е. мы сделали 7 шагов до 1, а в последовательности имеем 8 чисел(именно кол-во чисел программа и считает, если это количество больше 255, тогда заканчиваем вичисления).

C

#include<stdio.h>
 
int collatza(int n){
        int cnt=0;
        asm volatile(
        ".intel_syntax noprefix;"
        "mov eax,%1;"
        "mov ebx,0;"
"start:"
        "cmp ebx,255;"
        "je FIN;"
 
        "cmp eax,1;"
        "je isOne;"
 
        "test eax,1;"
        "jnz nieP;"
        "jz takP;"
 
"nieP:"
        "mov ecx,eax;"
        "add eax,eax;"
        "add eax,ecx;"
        "add eax,1;"
        "add ebx,1;"
        "add ebx,1;"
        "shr eax;"
        "jmp start;"
 
"takP:"
        "shr eax;"
        "add ebx,1;"
        "jmp start;"
 
 
        "isOne:"
        "add ebx,1;"
        "FIN:"
        "mov %0,ebx;"
 
 
        ".att_syntax prefix;"
        :"=r"(cnt)
        :"r"(n)
        :"eax","ebx","ecx"
        );
return cnt;
}
int main(){
unsigned char wynik[65536];
int i;
        for(i=0;i<65536;++i){
                wynik[i]=collatza(i+1);
        }
return 0;
}

Напишу псевдокод алгоритма, который написан на ассемблере:

C

start:
if(counter==255)goto FIN;
if(n==1)goto isOne;
if(n%2==1)goto nieP
else goto takP
 
nieP:
int e = n;
n=n+n;
n=(n+e)/2;
counter = counter + 2;
goto start;
 
takP:
n=n/2;
counter++;
goto start;
 
isOne;
counter++;
FIN:

Мои скромные знания ассемблер позволили данный код оптимитизировать до такой степени, в которой Вы его видите сейчас. Вопрос таков, подскажите советом или идеей, как ещё возможно оптимизировать данный код на ассемблер, чтобы программа заработала быстрее????

Добавлено через 8 минут
Вот такая вот идея, а что если перейти на нижние регистры, т.е. например вместо eax везде написать al итд?????

@Hadros · 16.12.2015, 12:48

Assembler

        mov     ecx,255
  @start:
        dec     ecx
        jz      @finish
        shr     eax,1
        jz      @finish
        jnc     @start
        lea     eax,[2*eax+eax+2]
        dec     ecx
        jnz     @start
  @finish:
        mov     eax,ecx
        not     al

Начальное число в EAX, ответ в AL.
По моим тестам вышло вроде как на 30 процентов быстрее. Но у вас там ошибка: в 25-26 строка увеличивается EBX, но не проверяется, чему он стал равен. Поэтому нормально сравнить по скорости не получилось.

	16.12.2015, 12:48

Оптимизация программы(Гипотеза Коллатца)

Решение