Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)

• To: mathgroup at smc.vnet.net
• Subject: [mg49668] Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
• From: "Alex Vinokur" <alexvn at big-foot.com>
• Date: Tue, 27 Jul 2004 07:00:49 -0400 (EDT)
• References: <7f4ffu\$6dj\$1@nnrp1.dejanews.com>, <Mo2OZGACWlF3Ewez@raos.demon.co.uk>, <7g0qsd\$dr9@smc.vnet.net> <cdvm0e\$7hv\$1@smc.vnet.net> <ce2ftd\$8rh\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```"Michael Taktikos" <michael.taktikos at hanse.net> wrote in message news:ce2ftd\$8rh\$1 at smc.vnet.net...
> Alex Vinokur <alexvn at bigfoot.com> wrote:
>
> > >> >Several large Fibonacci numbers were calculated using only
> > >> >the well-known explicit formula:
> > >> >        Fib (0) = 0, Fib (1) = 1,
> > >> >        Fib (n) = Fib (n-1) + Fib (n-2), n >= 2
> > >> >All the (decimal) digits of these numbers were obtained.
> [...]
> > >> >But to get ALL digits of the large Fibonacci number is very
> > [C++ code, snip]
>

Impoved version of that algorithm can be seen at

> Until now, the fastest way to get with "Mathematica-alone" all digits of
> large Fibonacci numbers seems to be that of Roman Maeder:
>
> ********************************************************
> fibmaeder[n_] :=
>  Module[{r11 = 1, r12 = 0, r22 = 1, digits = IntegerDigits[n-1, 2], i, t},
>   Do[ If[ digits[[i]] == 1,
>           {r11, r22} = {r11(r11 + 2r12), r12(r11 + r22)};
>           r12 = r11 - r22
>         , t = r12(r11 + r22);
>           {r11, r12} = {r11(r11 + 2r12) - t, t};
>           r22 = r11 - r12
>         ],
>      {i, Length[digits]-1}
>     ];
>   If[ digits[[-1]] == 1,
>       r11(r11 + 2r12),
>       r11(r11 + r22) - (-1)^((n-1)/2)
>   ]
>  ]
>
[snip]

I would like to measure the comparative performance of my C++ algorithm and "Mathematica-alone" code above.
However I have never worked with "Mathematica-alone".
How can I compare those algorithms?

--
Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

```

• Prev by Date: Re: Q: extract all k-tuple from a list of n elements
• Next by Date: Re: Slow LinearSolve.
• Previous by thread: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
• Next by thread: Re: Re: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
{"ft_lang_label":"__label__en","ft_lang_prob":0.6646597,"math_prob":0.9578761,"size":2492,"snap":"2020-24-2020-29","text_gpt3_token_len":891,"char_repetition_ratio":0.16278136,"word_repetition_ratio":0.10497238,"special_character_ratio":0.4398074,"punctuation_ratio":0.24177949,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99325645,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-05T01:41:02Z\",\"WARC-Record-ID\":\"<urn:uuid:5ef7f22d-a5b6-4be7-8709-3edb0e10fe57>\",\"Content-Length\":\"46902\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b727a655-e4a3-47f9-a63e-1cbfdeb1707f>\",\"WARC-Concurrent-To\":\"<urn:uuid:330166ff-7d3c-40e4-965f-1eb86884b6bc>\",\"WARC-IP-Address\":\"140.177.205.73\",\"WARC-Target-URI\":\"http://forums.wolfram.com/mathgroup/archive/2004/Jul/msg00585.html\",\"WARC-Payload-Digest\":\"sha1:SFOYVAY2FEQPADN2Q23RRX26LLSW5ZE6\",\"WARC-Block-Digest\":\"sha1:M6JDS7A6GD5A4IZYLAYBWRC5PP76S7FM\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593655886802.13_warc_CC-MAIN-20200704232817-20200705022817-00013.warc.gz\"}"}