Числа Фибоначчи - это последовательность целых чисел, определяемая следующим образом:

F₀=0
F₁=1
F_n+2=F_n+1+F_n, n - целое неотрицательное число.

Задан адрес, обозначим его ADDR, по которому нужно поместить таблицу чисел Фибоначчи от F₀ до F₄₇, размер чисел - dword. То есть по адресу ADDR поместить значение F₀=0, по адресу ADDR+4 - значение F₁=1, и т. д.

Оптимизировать код по размеру. Предлагая вариант, указывать размер в байтах...

Справка ("откуда взялось число 47"): F₄₇ - максимальное число Фибоначчи, влезающее в беззнаковый dword (но не помещающееся в знаковый).

        mov edi,table   ;5

        xor eax,eax     ;2
        lea ecx,[eax+1] ;3
    .fib:
        stosd           ;1
        xchg eax,ecx    ;1
        add eax,ecx     ;2
        jnc .fib        ;2

Итого 11 байт без команды загрузки адреса таблицы

Я, с вашего позволения, начну как новичок в этих делах. Самый очевидный (и не совсем правильный, кстати) метод выглядит так:

	unsigned n1 = 0;
	unsigned n2 = 1;
	unsigned n3 = 0;

	do{
		n3 = n1 + n2;
		n1 = n2;
		n2 = n3;
		printf("%u\n", n3);
	}while(n3 < INT_MAX);

Что сводится к следующему ассемблерному коду:

xor	 ebx, ebx
mov	 edi, 1
@again:
lea	 esi, DWORD PTR [edi+ebx]
mov	 ebx, edi
mov	 edi, esi
cmp	 esi, -2147483648	; 80000000H
jb	 @again

Итого: 15 байт из которых хренова туча именно на cmp.
Т.е. нужно заменить cmp/jb на что-нибудь менее ужасное, что детектило бы overflow. Так можно отыграть где-то три байта или что-то около.

Сейчас будет второй вариант.

Black_mirror

Ты меня опередил, я хотел начать :((((

Вариант с массивом, в котором убирается проверка на overflow в принципе, выглядит так:

    int i;
    int fib[47];

    fib[0] = 1;
    fib[1] = 1;

    for (i = 2; i < 47; i++)
    {
        fib[i] = fib[i-1] + fib[i-2];
    }

Однако индексы сводят отказ от проверки на ноль :( Или даже на минус. Щаз поглядим как оно будет с поинтерами работать :)

Оптимизированный вариант на С без индексов выглядит так:

    int fib[47];
	
    fib[46] = '$';
    fib[0] = 1;
    fib[1] = 1;

    int *fib_p = &fib[2];
    while(*fib_p != '$')
    {
        *fib_p = *(fib_p-2) +  *(fib_p-1);
	fib_p++;
    }

Само тело цикла сводится к:

@cool:
mov	 edx, DWORD PTR [eax-8]   ;3
add	 edx, DWORD PTR [eax-4]   ;3
mov	 DWORD PTR [eax], edx     ;2
mov	 edx, DWORD PTR [eax+4]   ;3
add	 eax, 4                   ;3
cmp	 edx, ecx                 ;2
jne	 @cool                    ;3

xadd используйте.

Сократил вариант Black_mirror на байт.
Не пойму только, как XADD может уменьшить размер, она же 3 байта?

	mov	edi, ADDR	; 5	
	xor	eax, eax	; 2	
	cdq			; 1	
	inc	edx		; 1	
@@:	stosd			; 1	
	xadd	eax, edx	; 3	
	jnb	@b		; 2	

volodya
>fib[0] = 1;
нужно fib[0] = 0; :)

    mov   edi,addr

    sub   eax,eax     ; 2
    stc               ; 1
@@: stosd             ; 1
    adc   eax,[edi-8] ; 3
    jnc   @b          ; 2

Если предположить, что по addr-4 лежит ноль, то 9 байт.. иначе 10. Я седня туплю хуже обычного, извините если что :(

Не пойму только, как XADD может уменьшить размер, она же 3 байта?
:)
Ну вот ты сам мне ответь убедившись, что xadd эвкиваленто будет по функцианальности и размеру паре команд add и xchg ты сам то что предпочтёшь написать в программе?
vaskovich - не сработает.

The Svin
Ээ.. почему? У меня все работало, т.е. получилась последовательность 0,1,1,2,3,5,8,13,... Или ты имеешь ввиду что такое мое допущение тут никому нафиг не нужно?
В целом разъясни фразу.

ozzman

Неа. И так работает :)
Да, и еще.

while(n3 < INT_MAX + 1)

надо заменить на:

while(!(n3 & INT_MAX + 1))

отыграем три байта.

vaskovich
ваш код выдает правильные числа до F₃₁ включительно.