VS2008 WM fibonacci duże liczby

Mam problemik wynikający z mojej aktualnej niewiedzy i braku doświadczenia. To mój drugi program więc dopiero zaczynam. Dla nauki tworze aktualnie program na windowsa mobile.

Jest to program który oblicza zadaną liczbę ciągu fibonacci'ego.
Mam dwa textboxy oraz przycisk oblicz. W textbox1 wpisuje szukaną liczbę. Klikam oblicz i textbox2 wyświetla tą liczbę.

I teraz problem jest taki, że te liczby ciągu fibonacci'ego szybko "rosną" szybko wykorzystując standardowe typy zmiennych. Czyli zwykły int pozwala na obliczenie do 46 liczby a ulong do 94.
Zakładam, że 0 jest pierwszą liczbą ciągu.

Mój kod wygląda tak:

private void button1_Click(object sender, EventArgs e)
        {
            int liczba = Convert.ToInt32(textBox1.Text);
            if (liczba <= 0)//||(liczba>94))
            {
                textBox6.Text = "Wprowadź właściwą liczbę!";
            }
            else if (liczba == 1)
            {
                textBox6.Text = "0";
            }
            else
            {
                ulong f1 = 0;
                ulong f2 = 1;
                for (int i = 2; i <= liczba; i++)
                {
                    ulong m = f2 + f1;
                    f1 = f2;
                    f2 = m;
                    textBox6.Text = m.ToString();
                }
            }
        }

No i teraz potrzebuje pomocy bo nie wiem jak zrobić to na tablicach (chyba tak to się nazywa).
Wiem, że można stworzyć tablicę która będzie zawierać te liczby. Jak to zrobić by te tablice zawierające kolejne liczby ciągu do siebie dodawać?
Znalazłem takie coś http://edu.i-lo.tarnow.pl/inf/alg/001_search/0024.php
Na stronie w przeglądarce można obliczać naprawde duże liczby, ale nie potrafię tego przerobić na swoje potrzeby.

Generalnie jest to zły sposób na wyznaczanie n-tego wyrazu ciągu Fibonacchiego, bo algorytm ma złożoność liniową O(n), podczas gdy da się to obliczyć w czasie stałym O(1).

gdzie to Math.Floor()

Mogę poprosić o jakieś przykłady?

Przyklady czego ? Zastosowania wzoru matematycznego ?! Przeciez tam nie ma nic skomplikowanego - pierwiastek, potegowanie, ulamki i to Math.Floor()... a, no i dodawanie.

Wiesz nie widzę jak to rozwiązuje problem wyświetlenia liczby F(n) wiekszej niż ulong. Jeżeli się mylę to proszę o oświecenie.

Duże liczby są w klasie java.math.BigInteger
Żeby uzyskać do niej dostęp, należy w projekcie dodać referencję do biblioteki vjslib
Na docelowym komputerze oprócz .Net Framework będzie potrzebny też zainstalowany J# Runtime.

using System;
using java.math;

class Program
{
    static void Main()
    {
        var big1 = new BigInteger("500000000000000000000000000000000000000000000000000000000000000000000");
        var big2 = new BigInteger("1231231231231231231231231231231233211232132222123112123123");
        var big3 = big1.multiply(big2);
        Console.WriteLine(big3);
        Console.ReadKey();
    }
}

w Visual Studio 2010 i .Net 4.0 doszedł typ System.Numerics.BigInteger, który w przeciwieństwie do powyższego, ma przeciążone operatory.

BigIntegery są też w .NET 4.0. Co je ogranicza z góry, to tylko wielkość pamięci potrzebnej na przechowanie liczby :)

//edit: a, Azarien już o tym wspomniał, nie doczytałem do końca...

Ale, jeśli mówimy o Windows Mobile to ani J# runtime, ani .NET 4.0 nie są dla niego dostępne. Trzebaby napisać własny odpowiednik takiej klasy... może już ktoś to zrobił nawet:

http://www.codeproject.com/KB/cs/biginteger.aspx
http://intx.codeplex.com/

@Azarien napisał

Generalnie jest to zły sposób na wyznaczanie n-tego wyrazu ciągu Fibonacchiego, bo algorytm ma złożoność liniową O(n), podczas gdy da się to obliczyć w czasie stałym O(1).

gdzie to Math.Floor()

Możesz wyjaśnić dlaczego n-krotne mnożenie jest lepsze od n-krotnego dodawania?

Możesz wyjaśnić dlaczego n-krotne mnożenie jest lepsze od n-krotnego dodawania?

Nie mogę. Ale mogę przeprowadzić test, dla liczb np. 200-cyfrowych. Jak czas znajdę…

bo napisał(a)

Możesz wyjaśnić dlaczego n-krotne mnożenie jest lepsze od n-krotnego dodawania?

Zawsze można zastosować algorytm szybkiego potęgowania i wtedy mamy log n mnożeń, jedno dzielenie i jedno dodawanie zamiast n dodawań.

Wynik testu (Java, klasy BigInteger i BigDecimal), nie optymalizowałem mnożenia, tylko wywoływałem metodę pow() klasy BigDecimal. Możliwe, że metoda sama optymalizuje.

c:\kody źródłowe\java\matematyczne>java Fibonacci 100
Czas wykonania (w nanosekundach): 1134502 (dodawanie)
Czas wykonania (w nanosekundach): 73543425 (mnozenie)

c:\kody źródłowe\java\matematyczne>java Fibonacci 1000
Czas wykonania (w nanosekundach): 2484953 (dodawanie)
Czas wykonania (w nanosekundach): 5862745126 (mnozenie)

c:\kody źródłowe\java\matematyczne>java Fibonacci 10000
Czas wykonania (w nanosekundach): 16684523 (dodawanie)
Czas wykonania (w nanosekundach): 618476181470 (mnozenie)

Wyższość mnożenia nad dodawaniem jest mocno wątpliwa.

Azarien:
Twój sposób wymaga liczb zmiennoprzecinkowych. BigInteger chyba taką nie jest. No i złożoności stałej na pewno nie ma. Sama długość liczby F(n) jest liniowa względem n.

Czemu nie skorzystacie z metody z mnożeniem macierzy?
http://www.ideone.com/ej7Zs
Przyjmuje indeks liczby Fibonacciego, a wypisuje najpierw przybliżoną długość liczby w cyfrach, a potem całą liczbę.

BigInteger.multiply jest prawdopodobnie dość nieefektywną implementacją, co najwyżej Karatsuba (a i w to wątpię), nie mówiąc już o czymś opartym na FFT.

Czas dla obliczenia 1234567-ej liczby Fibonacciego to 14 sekund u mnie. Pewnie metoda z dodawaniem będzie szybsza, bo nie wymaga FFT, ani innych "sztuczek", których w Sunowskiej Javie nie ma.

Edit:
Znalazłem Karatsubę na necie w Javie i dołożyłem:

import java.io.IOException;
import java.math.BigInteger;

class FibonacciMatrix {

    private final BigInteger a11, a12, a21, a22;

    public FibonacciMatrix() {
        this(BigInteger.ONE, BigInteger.ZERO);
    }

    private FibonacciMatrix(BigInteger a21, BigInteger a22) {
        this.a11 = a21.add(a22);
        this.a12 = a21;
        this.a21 = a21;
        this.a22 = a22;
    }

    public BigInteger getResult() {
        return a12;
    }

    private static BigInteger karatsuba(BigInteger x, BigInteger y) {

        // cutoff to brute force
        int N = Math.max(x.bitLength(), y.bitLength());
        if (N <= 2000) {
            return x.multiply(y);                // optimize this parameter
        }
        // number of bits divided by 2, rounded up
        N = (N / 2) + (N % 2);

        // x = a + 2^N b,   y = c + 2^N d
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));

        // compute sub-expressions
        BigInteger ac = karatsuba(a, c);
        BigInteger bd = karatsuba(b, d);
        BigInteger abcd = karatsuba(a.add(b), c.add(d));

        return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2 * N));
    }

    private FibonacciMatrix multiply(FibonacciMatrix that) {
        return new FibonacciMatrix(
                karatsuba(this.a11, that.a21).add(karatsuba(this.a12, that.a22)),
                karatsuba(this.a21, that.a12).add(karatsuba(this.a22, that.a22)));
    }

    public FibonacciMatrix power(int power) {
        FibonacciMatrix squaring = this;
        FibonacciMatrix result = new FibonacciMatrix(BigInteger.ZERO, BigInteger.ONE);
        while (true) {
            if ((power & 1) == 1) {
                result = result.multiply(squaring);
            }
            power /= 2;
            if (power == 0) {
                break;
            }
            squaring = squaring.multiply(squaring);
        }
        return result;
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        int number = Integer.valueOf(args[0]);
        BigInteger result = new FibonacciMatrix().power(number).getResult();
        //System.out.println(((float) result.bitLength()) * Math.log10(2));
        //System.out.println(result);
    }
}

Wywołane z parametrem 12345678 wykonuje się ok 26 sekund u mnie.

PS: new FibonacciMatrix(BigInteger.ZERO, BigInteger.ONE) w rzeczywistości tworzy macierz identyczności!!!

Panowie dużo sopie pogadaliśmy. Już druga strona leci :)
Tu podaje gotowe rozwiązanie. Czy dobre? (pytanie retoryczne) Pewnie słów krytyki można dużo powiedzieć. Generalnie działa. Podziękowania dla "mykhaylo"
Kod przycisku który rozpoczyna liczenie:

private void button1_Click(object sender, EventArgs e)
 {
 int liczba = Convert.ToInt32(textBox1.Text);
 if (textBox1.Text.Length < 1)
 {
 textBox6.Text = "Wprowadź liczbę większą od zera!";
 }
 else if (liczba < 1 )
 {
 textBox6.Text = "Wprowadź liczbę większą od zera!";
 }
 else if (liczba == 1)
 {
 textBox6.Text = "0";
 }
 else if (liczba == 2)
 {
 textBox6.Text = "1";
 }
 else
 {
 string f = String.Empty, f0, f1;
 int i;
 f0 = "0"; f1 = "1";
 textBox6.Text = "Obliczam. Proszę czekać...";
 for (i = 2; i < liczba; i++)
 {
 f = Add(f0, f1);
 f0 = f1;
 f1 = f;
 }
 textBox6.Text = f.ToString();
 }
 
}

Kod sumy:

private static String Add(string a, string b)
 {
 int ia, ib, p, s;

 ia = a.Length - 1; ib = b.Length - 1;
 String c = ""; p = 0;
 do
 {
 s = 0;
 if (ia >= 0) s = a[ia--] - 48;
 if (ib >= 0) s += b[ib--] - 48;
 s += p;
 if (s > 9)
 {
 p = 1; s -= 10;
 }
 else p = 0;
 c = (char)(s + 48) + c;
 } while ((ia >= 0) || (ib >= 0) || (p != 0));
 return c;
 }

PS
nie moge tu załącznika dodać z gotowym programem.
http://www.przeklej.pl/plik/fibonfun-7z-0020td4i71dc - FibonFun v1.1
Program dziala na WM6/6,5 oraz Windows XP/Vista/7/Server :P

mozna tez miec ileś pierwszych liczb ciagu w statycznej tablicy (np. 20)

dla ulongów czas dodawania jest średnio o > 20% krótszy od mnożenia...

sorry - nie odświeżyłem wątku;)

Też tak słyszałem ze procesory wolą dodawać niż mnożyć - taka ich kontrukcja. Lepiej jeżeli musimy zrobić Ax2 wykonać A+A. Przy pojedynczym dzialaniu no problem ale w dużych obliczeniach ma to juz znaczenie podobno.

Akurat kompilator, o ile nie jest badziewny, powinien zoptymalizować "a * 2" na "a + a", a mnożenia/ dzielenia przez potęgi dwójki na przesunięcia bitowe.

Mimo wszystko liczy się złożoność.

Wersja prosta z dodawaniem ma złożoność O(n^{2) względem długości wyniku (n dodawań liczb o średniej długości n / 2), a moja wersja z użyciem Karatsuby ma złożoność około O(lg lg n * n}1.585) - jest O(lg lg n) mnożeń macierzy, a każde mnożenie zajmuje O(n^1.56).

Dla n = 12345678:
n^{2 = 1.52415765 × 10}14
lg lg n * n^{1.585 = 7.54091304 × 10}11

Różnica ogromna i nawet biorąc pod uwagę stałe to i tak mój jest szybszy.

Aktualny kod wersji 1.3

Poprawiony błąd wywalający program jeżeli nie wpiszemy żadnej liczby oraz dodana możliwość wyboru czy obliczamy ciąg, którego początkiem jest "0" albo "1".

FibonFun_v1.3 do pobrania tu - http://www.przeklej.pl/plik/fibonfun-v1-3-zip-00241s4vi96u

        private void button1_Click(object sender, EventArgs e)
        {
            int p;
            if (radioButton2.Checked)
                {
                p = 1;
                }
            else
                {
                p = 0;
                }
            if (textBox1.Text.Length < 1)
            {
                textBox6.Text = "Wprowadź liczbę!";
            }
            else
            {
                int liczba = Convert.ToInt32(textBox1.Text);
                if (liczba < 1)
                {
                    textBox6.Text = "Wprowadź liczbę większą od zera!";
                }
                else if (liczba == 1 && p == 0)
                {
                    textBox6.Text = "0";
                }
                else if (liczba == 1 && p == 1)
                {
                    textBox6.Text = "1";
                }
                else if (liczba == 2)
                {
                    textBox6.Text = "1";
                }
                else
                {
                    string f = String.Empty, f0, f1;
                    int i;
                    if (p == 0)
                    {
                        f0 = "0"; f1 = "1";
                    }
                    else
                    {
                        f0 = "1"; f1 = "1";
                    }
                    textBox6.Text = "Obliczam. Proszę czekać...";
                    for (i = 2; i < liczba; i++)
                    {
                        f = Add(f0, f1);
                        f0 = f1;
                        f1 = f;
                    }
                    textBox6.Text = f.ToString();
                }
            }
            
        }

        private static String Add(string a, string b)
        {
            int ia, ib, p, s;

            ia = a.Length - 1; ib = b.Length - 1;
            String c = ""; p = 0;
            do
            {
                s = 0;
                if (ia >= 0) s = a[ia--] - 48;
                if (ib >= 0) s += b[ib--] - 48;
                s += p;
                if (s > 9)
                {
                    p = 1; s -= 10;
                }
                else p = 0;
                c = (char)(s + 48) + c;
            } while ((ia >= 0) || (ib >= 0) || (p != 0));
            return c;
                    
        }

        private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
        {
            if (e.KeyChar >= '0' && e.KeyChar <= '9' || e.KeyChar == 8)// Sprawdzamy czy wciśnięty jest liczbą albo klawiszem backspace
            {
                e.Handled = false;                                     // Nie blokujemy znaku
            }
            else
            {
                e.Handled = true;                                    // W przeciwnym wypadku blokujemy znak
            }
        }