staging.inyokaproject.org

Ja audax ,sry ich hatte erst 10000 drin stehen 😉

int kann schon recht groß werden 😉

Ausserdem hat Hello World recht am Anfang dieses Themas schon fest gestellt, dass long long nicht für die 100. Fibonacci-Zahl ausreicht. Jedenfalls nicht, wenn es "nur" 64-Bit sind.

Joa ich wusste aber nicht was das programm rauswirft 😉

Dann werd ich mir mal die anderen codes genauer angucken

Hmm selbst mit dem C++ beispiel kann ich nichts anfangen ☹

Nochmal für meine Brotkiste... man hat f1=0 und f2=1 die werden beide addiert zu f3=f1+f2

dann hat man 1 und dann wird f2 +f3 gerechnet oder?

und da bleib ich hängen ☹

Hängt die größe von einem int in C nicht vom Compiler ab?
Soweit wie ich mich erinnere ist doch im ANSI Standard nur geregelt wieviel Bytes die unterschiedlichen Typen Minimum haben müssen. Nach oben hin können diese aber je nach Compiler doch auch beliebig groß werden?

@Ghaldez
Verstehst du Generell die Fobonacci folge nicht?
Diese ist eigentlich ganz simpel. Die Nächste zahl wird aus den letzten beiden Zahlen zusammen gerechnet.
Du fängst mit (1, 1) an. Die nächste Zahl sind die letzten beide addiert. Also 1 + 1. Dann hast du (1, 1, 2). Die nächste Zahl ist wieder die letzten beiden Addiert. "1 + 2". Ergebnis:
(1, 1, 2, 3). Die nächste Zahl ist wieder die letzten beide Addiert. (2 + 3). Ergebnis: (1, 1, 2, 3, 5) u.s.w.

Ums ihm nicht zu verderben nur als Link:
Meine C-Variante 😉
http://paste.pocoo.org/show/30690

@sid_burn WTF !!1111 was hast du denn für nen Rechner \^^. Wenn ich nicht total auf dem Holzweg bin, sollte die Komplexität der Rekursive Berechnung exponentiell wachsen. Da unterstell ich doch Perl, dass es heimlich auf iterativ optimiert hat 😉.
Ah, ne seh gerade du lässt die Ergebnisse cachen \^^, ich war schon echt von den Socken *phew*.

Dann sag ich mal, nicht die Art von Berechnung die ich meinte, aber trotzdem ne coole Lösung 😉

Wenn wir schon beim Längenvergleich von rekursiven Lösungen für grosse Zahlen sind:

-module(fib2).
-export([fib/1,start/1]).

fib(N) ->
    fib(1,1,N).

fib(F1,_,1) ->
    io:format("~w~n", [F1]);

fib(F1,F2,N) ->
    FN = F1+F2,
    fib(F2,FN,N-1).


%%%

start([H|_]) ->
    N= list_to_integer(atom_to_list(H)),
    io:format("fib(~w)=~n", [N]),
    fib(N),
    init:stop().

Ach, und

 time erl -noinput -s fib2 start 100000
fib(100000)=
25974069347221724....
.....
[Viele weitere Zeilen]
.....
14383883939018953166274355609970015699780289236362349895374653428746875

real    0m2.470s
user    0m1.387s
sys     0m0.029s

Yeah. 2,5 Sekunden für *hunderttausend*. Automatisches Auflösen von Tail Recursion rules 😀
Und von den 2 Sekunden gehen knapp 1 für geordneten Start und Shutdown des Laufzeitsystems drauf.

@audax Was hat denn bei deiner CPP Implementierung double für ne Genauigkeit?
Also ich hab nachgeschlagen, dass double häufig 2^64 Speichergröße hat, damit wären wir bei unsigned mit maximal
1.84467441e19 dabei f(99) ist bei mir aber Im Bereich von 10e21 😉

ich benutz, wenn überhaupt, C 😉
ein sizeof gibt bei mir auch 8 Bytes, aber er läuft nicht über Oo

So dann bin ich mal dran ☺

#include <iostream>
#include "bignum.h"
using namespace std;

int main()
{
      bignum *numbers[11000];
      numbers[0] = new bignum("0");
      numbers[1] = new bignum("1");
      for ( int i = 2; i <= 10999; i++ ) {
	  numbers[i] = new bignum();
	  if( i > 3 ) delete numbers[i-3];
	  cout << endl;
	  *numbers[i] = *numbers[i-1]+*numbers[i-2];
	  cout << i << ". : " << numbers[i]->erase_null() << endl;
      }

      return 0;
}

Mit C++ (Klasse bignum habe ich selbst geschrieben ☺ ) dauert etwas weniger als eine Minute bis zur 10999. Zahl... Die sieht dann so aus:

10999. : 2021017654770797478028651223095495329175568954785215307070592977240383
9101769429014402739152166728057269294648883597608221210150398060009986708998724939
9330931220427432115154027586753046590863148727430818027149761959231592248141301198
7932403992321924044605434990897406435626091169987508895478096883363159145160160569
5799321611016271401185228792510415965957127675765288978183317554333188379158573139
7797305686018869921835146143360930629378948453643126215473701642797025307142773782
4511028482413647399469768089904138068494887914251756339357633268057441986399293316
3043270353754490517615564631334251709787557024644540058761385078998892319070397514
8413574886397408413874084292035383873096288501086755760509668450585279134313809815
6239254718114800055109313466748711982138905855262389492935871777061961690843917667
2557074072870200771178127869494714893473049447358027342982475804141242011105120231
2211826760625134995247799670260270368826675658373394026917597208913811059731731346
2330210171118773939549409446150625670126031003282140673874620849633193135854880798
1172508119125062235127184844083458080347890128122739229971564646293282493606087834
5216415937165067818246179358902224538260637680052522835312415987782657654689684573
7779637848268536888423039167398914385198843688730582423425175226612180720112241087
4266084691662761699478681374726372998701519374685856280496836148168723778058952546
2154994219051929211704292283238133706956610706319963651147063912034915374767080617
7734806724148008022947951843681668072571310888013684066823133382494747849902081807
0738817398308920381514164903533820621052193545131392095990028812280010449676631517
5314347709499753757204440230235203459922777432078438443987333455095669584671685886
0135550188105466218540638681543442053207236027087087468524722221231691606013073472
7994144340863270903304599670947521519470671434198211860923504397007534488935968872
8977924289227198012145182809903539583083723002842801781486859332876745462140263992
8543370656000543719596487882988880102775177047131375683867521729690067619411175891
3327652880016826113439126163596017329690720942854867756888447048243764386136965170
5020558341035797369041256843444532942030005098864151691121660471538259722823582266
1491759028107685320629464482747207747193311601392296772065475394069858973578638044
680452453811501

Tux90 hat geschrieben:

Mit C++ (Klasse bignum habe ich selbst geschrieben ☺ ) dauert etwas weniger als eine Minute bis zur 10999. Zahl...

from itertools import islice

def nth(iterable, n):
    "Returns the nth item or raise StopIteration"
    return islice(iterable, n, None).next()

def fibgen():
    n = m = 1
    while True:
        yield n, m
        n, m = m, n+m

print nth(fibgen(), 10998)[0]

dauert bei mir ~ 0.01s 😉

nun lass mich doch meinen Spaß haben 😀

Theoretisch könnte ich jede Zahl berechnen 😀 und da bin ich sehr stolz drauf ☺

@ Sid Burn , Ja Fibonacci hab ich verstanden nur wie ich es in C umsetzen soll nicht ganz.

@ Audax, das versteh ich nun ganz und garnicht !

Was ist double ? wärst du so nett es mir zu erklären ?

@audax: Du bekommst keinen Überlauf, aber die Zahlen stimmen nicht mehr, weil sich die grossen Zahlen nicht mehr genau als double darstellen lassen. Wenn man sich mal die 100. Zahl in (C) double (== Python's float) umwandelt und wieder zurück nach Ganzzahl, dann hat man in C ganze 14533 Häschen zu wenig:

In [33]: f100 = 573147844013817084101

In [34]: int(float(f100)) == f100
Out[34]: False

In [35]: f100 - int(float(f100))
Out[35]: 14533L

Wobei Dein Programm noch mehr daneben liegen kann, weil auf dem Weg zur 100. Zahl ja schon wiederholt mit ungenauen Werten gerechnet wird.

@Ghaldez: double ist ein ziemlich grundlegender Datentyp in C. Vielleicht solltest Du erst einmal ein Tutorial für C durcharbeiten. 😉

Eine C-Lösung mit der libgmp:

#include <stdio.h>
#include <gmp.h>

int main(void)
{
    int i;
    mpf_t a, b, tmp, golden_ratio;
    
    mpf_set_default_prec(200);
    mpf_init(a);
    mpf_init_set_ui(b, 1);
    mpf_init(tmp);
    mpf_init(golden_ratio);
    
    for (i = 0; i <= 100; i++) {
        mpf_set(tmp, b);
        mpf_add(b, b, a);
        mpf_set(a, tmp);
        
        mpf_div(golden_ratio, b, a);
        
        gmp_printf("%3d. %21.0Ff %.50Ff\n", i, a, golden_ratio);
    }
    
    mpf_clear(a);
    mpf_clear(b);
    mpf_clear(tmp);
    mpf_clear(golden_ratio);
    return 0;
}