Małe liczby Negafibonacciego

0

Witam,
Mam problem z jednym zadankiem:

"Należy policzyć liczby Fibonacciego F(n) mod 70001 dla ujemnych n. Należy skorzystać z faktu, ze F(-2k) = -F(2k) i F(-2k + 1) = F(2k - 1).
Oczywiście F(0) = 0, F(1) = 1 i F(n) = F(n - 1) + F(n - 2) dla n > 1.

Kolejne testy zawierają wartości n: do -104, do -107, do -1010"

Na wejście w kolejnych liniach podawane są n, wyjście to w kolejnych liniach obliczona przez program wartość.

Przykładowy input:
-3
-25
-187
-1000
-9998

I output:
2
5024
34789
31219
10430

Do long longa wejdzie chyba max 94 czy 93 liczba fibonacciego więc raczej nie trzeba tych liczb do końca obliczać.
Do tego limit wykonania programu to 1s.

Dodatkowo dostałem takie zależności:
F(2n) = F(n) (F(n) + 2 F(n - 1))
F(2n + 1) = F(n + 1)2 + F(n - 1)2

Proszę o rady czy sugestie.

0

F(n) = (F(n-1) + F(n-2)) % 70001
musisz liczyć do końca

a jakie może być n?

0

Dodam że piszę w C++.
n będzie mieć maksymalnie -1010
Najbardziej pojemna zmienna czyli long long trzyma maksymalnie 92 czy 93 liczbę fibonacciego.

0

ale liczysz modulo 70001, czyli tylko n nie mieści się w 32 bitach

0

F(95) nie mieści się w 64 bitach, a ja muszę policzyć F(1010) aby potem zrobić z niego mod 70001. Chyba że jest sposób na policzenie modula bez obliczania samego F(1010). Samo n czyli maksymalnie 1010 przechowam w 64 bitowym long longu.

Oraz

Xitami napisał(a)

F(n) = (F(n-1) + F(n-2)) % 70001
nie jest prawdą.
F(n) = F(n-1) + F(n-2)
dopiero wynik = F(n) % 70001.

1
#include <cstdlib>
#include <iostream>

const int Modulo = 70001;

int negafibo(int64_t n) {
    int former = 0, latter = 1, period = 0;

    do {
        former ^= latter ^= former ^= latter; // swap
        latter += former;
        latter = (latter >= Modulo) ? latter - Modulo : latter;
        period++;
    } while ((former != 0) || (latter != 1));

    int k = (n < 0 ? -n : n) % period;

    for (int i = 0; i < k; i++) {
        former ^= latter ^= former ^= latter; // swap
        latter += former;
        latter = (latter >= Modulo) ? latter - Modulo : latter;
    }

    return (((n & 1) == 0) && (n < 0)) ? (-former) : former;
}

int main(int argc, char** argv) {

    int64_t n;

    std::cin >> n;

    std::cout << negafibo(n) << std::endl;

    return EXIT_SUCCESS;
}

Okres jest stały (bo wartość dzielnika modulo jest stała), więc równie dobrze można go wbić na stałe. Okres to 35000.

expsid:
Załóż sobie np że liczmy nie w systemie dziesiętnym, ale 70001-kowym. Wtedy interesuje nas tylko ostatnia cyfra, wszystkie bardziej znaczące cyfry możemy od razu odrzucać, bo nie wpływają na tą ostatnią.

Jak na razie zapuściłem sobie programik liczący okresy i dla dzielników modulo od 2 do ponad pół miliona okresy istnieją - tzn okres to u mnie najmniejsze dodatnie k, takie że F(k) % dzielnik = 0 i F(k + 1) % dzielnik = 1. Bardzo możliwe, że okresy istnieją dla wszystkich dzielników.

Oto ten programik liczący okresy:

#include <cstdlib>
#include <iostream>

int negafiboperiod(int modulo) {
    int former = 0, latter = 1, period = 0;

    do {
        former ^= latter ^= former ^= latter; // swap
        latter += former;
        latter = (latter >= modulo) ? latter - modulo : latter;
        period++;
    } while ((former != 0) || (latter != 1));

    return period;
}

int main(int argc, char** argv) {

    for (int i = 2; i < 2000000000; i++) {
        int period = negafiboperiod(i);
        if (i % 1000 == 0) {
            std::cout << i << " " << period << std::endl;
        }
    }

    return EXIT_SUCCESS;
}

Liczy okresy dla kolejnych dzielników i wypisuje co tysięczną parę.

0

rozumiem, że zamiast int k = (n < 0 ? -n : n) % [b]Modulo[/b];
miało być int k = (n < 0 ? -n : n) %[b] period;[/b]

wydaje się, że tak można
gdy po policzeniu okresu otrzymamy former==0 i letter=1 to jest OK
okres zawsze się znajdzie ale może być wielki
zobacz np. dla i=68'450 period==210'900
pesymistycznie - kiepsko, średnio - tak sobie

wydaje mnie mi się, że lepiej wyjść od podanych wzorów lub potęgowania macierzy.

0

Dzięki za zwrócenie uwagi: tak miało być period a nie Modulo.

wydaje mnie mi się, że lepiej wyjść od podanych wzorów lub potęgowania macierzy.

No tak, potęgowanie macierzy będzie tutaj bardzo szybkie, wychodzi tylko O(lg n) mnożeń macierzy o stałym rozmiarze. Jednak mój sposób dla stałego Modulo osiąga czas generalnie O(1).

0

Na ideone.com ćwierć miliona fibonaccich poczynając od 2 miliardów w mniej niż sekundę

#include <stdio.h>
typedef unsigned long long int ULL;
#define M(a,b,c,d,N) ((ULL)a*b + (ULL)c*d)%N
#define TMUL(a,b,c,d,e,f,g,h,N) {unsigned int A=M(e,a,g,b,N), B=M(f,a,h,b,N), \
                                              C=M(e,c,g,d,N); d=M(f,c,h,d,N); \
                                              a=A; b=B; c=C;}

unsigned int fibonacci(ULL n, unsigned int mod){  // n<2^64, mod < 3'037'000'500
	if (n<2) return n;
	n--;
	unsigned int xa=1,xb=1,xc=1,xd=0,ra=1,rb=1,rc=1,rd=1;	
	while(n){
		if(n&1)
			TMUL(ra,rb,rc,rd,xa,xb,xc,xd,mod)
		n/=2;
		if(n==0) break;
		TMUL(xa,xb,xc,xd,xa,xb,xc,xd,mod)  //tu można by urwać jedno mnożenie
	}
	return rb;
}

int main(){
	unsigned long long i,j=0;
	printf("%d\n",fibonacci(1000000000,1000000000));printf("560546875\n");
	for(i=0;i<250000;i++)
		j+=fibonacci(2000000000+i,70001);
	printf("%8lld %12llu\n",i,j);
	return 0;
}
0

Niestety Panowie wkradł się nam pewien błąd. Otóż np -2 % 70001 = 69999!
Wystarczyło zmodyfikować linijkę codu Wibowita na:

return (((n % 2) == 0) && (n < 0)) ? Modulo - former : former; 

I wszystko śmiga.
Pozdrawiam.

0
expsid napisał(a)

...

Xitami napisał(a)

F(n) = (F(n-1) + F(n-2)) % 70001
nie jest prawdą.
F(n) = F(n-1) + F(n-2)
dopiero wynik = F(n) % 70001.

To jest prawdą!!!
Nawet gdybyśmy zamiast dodawania mnożyli też by tak można było.
Wibowit liczy tak samo, ale oszczędza dzielenia, skoro F(n-1) i F(n-2) są mniejsze od 70001 to wynik będzie mniejszy od 2*70001.
Wystarczy więc sprawdzić czy suma jest większa lub równa 70001 i o tyle ją właśnie pomniejszyć.

Coś tam było nie tak w programie Wibowita dla ujemnych, ale masz przecie wzory.
Program Wibowita nie jest w takiej postaci rozwiązaniem Twojego problemu (mój też nie, liczę dla nie ujemnych n).

Pomysł Wibowita polega na tym, że nie musimy liczyć F(n) tylko F(n % period), tu period==35000 czyli możemy zyskać gdy n>period.
Mało tego, możemy przygotować sobie tablicę fib[period], a wynik uzyskamy "natychmiast" F(n)=fib[n % period]

0

Spoko, nawet bez tablicy program zrobiony na bazie pomysłu Wibowita czyli z okresem miał na SPOJu czas 0.00s
Widocznie testy były bardzo małe.
Dziękuję wam jeszcze raz za pomoc.

1 użytkowników online, w tym zalogowanych: 0, gości: 1