pootle
Posts: 340
Joined: Wed Sep 04, 2013 10:20 am
Location: Staffordshire
Contact: Website

A little fun with REALLY big python numbers

Wed Oct 31, 2018 10:13 am

I was slightly intrigued by the fact that python integers are boundless. You can indeed use ludicrously large numbers.

try this (python 3 please):

Code: Select all

import sys
bn=int(sys.float_info.max)
print(bn)
print('there are',len(str(bn)), 'digits in this number')
bbn=bn*bn
print('this bigger number has',len(str(bbn)), 'digits')
Now where did I leave that infinite hotel?

User avatar
joan
Posts: 14348
Joined: Thu Jul 05, 2012 5:09 pm
Location: UK

Re: A little fun with REALLY big python numbers

Wed Oct 31, 2018 11:27 am

Code: Select all

$ python2 pootle.py 
179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368
('there are', 309, 'digits in this number')
('this bigger number has', 617, 'digits')
$ python3 pootle.py 
179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368
there are 309 digits in this number
this bigger number has 617 digits
$ 
$ python2
Python 2.7.15+ (default, Oct 2 2018, 22:12:08)
[GCC 8.2.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>>

$ python3
Python 3.6.7rc1 (default, Sep 27 2018, 09:51:25)
[GCC 8.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>

hippy
Posts: 6068
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A little fun with REALLY big python numbers

Wed Oct 31, 2018 12:10 pm

What most impressed me with Python's unlimited size integer support is that the old two's complement trick of 'bit-wise invert and add one to negate' actually works.

One day I'm going to read up on how Python represents numbers internally. That 'it just works' is good enough but it has me intrigued.

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Wed Oct 31, 2018 12:37 pm

hippy wrote:
Wed Oct 31, 2018 12:10 pm
One day I'm going to read up on how Python represents numbers internally. That 'it just works' is good enough but it has me intrigued.
I hope it uses the GNU multi-precision library GMP. For integers anyway. Floating point seems fixed so perhaps not MPFR.

I tried this: a million to the power of a million

print( 1000000**1000000 )

$ python3 try.py | wc -c
6000002

is 6 million digits that the biggest?

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Wed Oct 31, 2018 12:42 pm

hippy wrote:
Wed Oct 31, 2018 12:10 pm
What most impressed me with Python's unlimited size integer support is that the old two's complement trick of 'bit-wise invert and add one to negate' actually works.
Yes indeed, that is clever.

In C, -n and ~n + 1 and n * -1 and n / -1 all emit the same "neg" instruction.

hippy
Posts: 6068
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A little fun with REALLY big python numbers

Wed Oct 31, 2018 3:30 pm

hippy wrote:
Wed Oct 31, 2018 12:10 pm
One day I'm going to read up on how Python represents numbers internally. That 'it just works' is good enough but it has me intrigued.
This seems a fairly good starting point for anyone interested. It's all quite involved under the hood as one might expect -

https://rushter.com/blog/python-integer-implementation/

Heater
Posts: 13592
Joined: Tue Jul 17, 2012 3:02 pm

Re: A little fun with REALLY big python numbers

Wed Oct 31, 2018 3:53 pm

This is great.

Perhaps some Python head can confirm (or otherwise) that 1 + 2 + 3 + 4 + 5 + 6 + ..... to infinity equals -1/12.

Or that 1 + 2 + 4 + 8 + 16 + 32 + .... to infinity equals -1.
Memory in C++ is a leaky abstraction .

User avatar
Paeryn
Posts: 2698
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A little fun with REALLY big python numbers

Wed Oct 31, 2018 4:54 pm

jahboater wrote:
Wed Oct 31, 2018 12:37 pm
hippy wrote:
Wed Oct 31, 2018 12:10 pm
One day I'm going to read up on how Python represents numbers internally. That 'it just works' is good enough but it has me intrigued.
I hope it uses the GNU multi-precision library GMP. For integers anyway. Floating point seems fixed so perhaps not MPFR.
It doesn't use GMP, it has its own version. Internally it breaks it down into an array of either 15 bit digits (for 16-bit systems) or 30 bit digits (for 32 & higher bit systems). Also they are stored as positive values with the sign encoded in the size of the array (a negative size denotes a negative value).
Floating point uses whatever the host supports as double (so typically 64-bit IEEE-754).
She who travels light — forgot something.

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Thu Nov 01, 2018 8:05 am

I saw this
Since Python 3 there is no longer simple integer type, and all integers are represented as a bignum.
That means in Python3 adding 2 + 2 uses arbitrary precision arithmetic. Although I can see the simplicity, it seems a step backwards for performance, considering most integers are small.

I counted the instructions needed to execute "2 + 2"

Python 12,659
Python3 110,875

In C of course it takes zero instructions

hippy
Posts: 6068
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: A little fun with REALLY big python numbers

Thu Nov 01, 2018 1:28 pm

jahboater wrote:
Thu Nov 01, 2018 8:05 am
That means in Python3 adding 2 + 2 uses arbitrary precision arithmetic. Although I can see the simplicity, it seems a step backwards for performance, considering most integers are small.
That is said to be one of the reasons why Python 3 can be considerably slower than Python 2, 30% slower and worse for the same source.

The counterpoint would be that, a number which is held in a single array entry should not be much more onerous to handle than the same stored in an explicit word entry. A generic, and 'handles anything', solution should be just as fast as something optimised for single word entry numbers.

I would agree with that. It should mostly be moving a pre-test for 'is this optimised or not?' to a post-test 'have we finished?', mere instruction cycle differences at best. The advantage being in having a single routine, not optimised and generic cases, pseudo-code -

Code: Select all

if n.isOptimised:
  x = n.explicitValue
else:
  x = n.arrayValue[0]
  if abs(n.arraySize) > 1:
    ...

Code: Select all

x = n.arrayValue[0]
if abs(n.arraySize) > 1:
  ...
While this second may actually be slower, with the rest of what's going on, I can't see that it adds 30% to the total execution time.

This is why I am not convinced it is merely this number representation change which most people rush to blame for the decreased performance. There seems far more to it than that in my experience.

Heater
Posts: 13592
Joined: Tue Jul 17, 2012 3:02 pm

Re: A little fun with REALLY big python numbers

Fri Nov 02, 2018 1:24 pm

jahboater,
That means in Python3 adding 2 + 2 uses arbitrary precision arithmetic.
Not necessarily. For example Javascript only has one number type. The 64 bit float. However modern JS engines optimize that down to 32 bit integer operations, where they can, at run time.

With this code:

Code: Select all

def recur_fibo(n):
    if n <= 1:
        return n
    else:
        return(recur_fibo(n-1) + recur_fibo(n-2))

nterms = 37
for i in range(nterms):
    print(recur_fibo(i))
I'm seeing a slow down of about 20% with Python 3. Which is quite a shocking hit for a new language version.

Especially shocking since Javascript under node.js can do it 16 times faster than Python2 !

Code: Select all

function recur_fibo(n) {
    if (n <= 1)
        return n
    else
        return(recur_fibo(n-1) + recur_fibo(n-2))
}

let nterms = 37
for (let n = 0; n < nterms; n++) {
    console.log(recur_fibo(n))
}
Python eats processor power and causes global warming.
Memory in C++ is a leaky abstraction .

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Fri Nov 02, 2018 3:38 pm

Yes, I also see JS is 20.6 times faster than Python2 for this program.

When I run the Javascript version there is a long delay before anything gets printed.
The Python numbers start immediately.
It looks like node is spending time optimizing the code first, perhaps even the whole file?
Unusual for an interpreter. And the JS syntax is nicer too.

Code: Select all

Pi3+
           
Python   134.59 sec
Python3  155.30 sec
node.js    6.53 sec
C (-O0)    2.21 sec
C (-O2)    0.68 sec
For me though I don't really care how slow Python is. Bash scripts also are pretty slow, but they have their uses, just like Python does.

Perhaps some of that initial delay is the load time for the interpreter:-
Node is quite large:-
File size of /usr/bin/node is 3828 blocks of 4096 bytes
File size of /usr/bin/python is 774 blocks of 4096 bytes
File size of /usr/bin/python3 is 971 blocks of 4096 bytes
The C executable is only 2 blocks, so the interpreters have to load quite a bit of stuff off the disk by comparison.

Heater
Posts: 13592
Joined: Tue Jul 17, 2012 3:02 pm

Re: A little fun with REALLY big python numbers

Fri Nov 02, 2018 6:47 pm

jahboater,
When I run the Javascript version I see a long delay before anything gets printed
That is interesting.

If I reduce the iterations down to just one I find Python gets a result 2 or 3 times faster than node.

As you say, I think node is spending more time at start up to optimize things.

Which is fair enough, for the use cases that node was created for programs are expected to run forever. So a little over head in start up is a good trade off.
For me though I don't really care how slow Python is...
Yep. For a rarely run script that produces a result in milliseconds or seconds nobody much cares about the difference between languages and run times.

However it distresses me to see people struggling to use Python in the robots and such, where speed can be of the essence, getting themselves all tangled up in threads and such. It's so much easier and faster to do this in JS.

You started me wondering... what if we used C as a kind of scripting language? Then we should measure the time it takes to get from source code to a result. Let's see:

Code: Select all

$ cat fibo.js
function recur_fibo(n) {
    if (n <= 1)
        return n
    else
        return(recur_fibo(n-1) + recur_fibo(n-2))
}

let nterms = 1
for (let n = 0; n < nterms; n++) {
    console.log(recur_fibo(n))
}

$ time node fibo.js
0

real    0m0.189s
user    0m0.047s
sys     0m0.141s

$ cat fibo.c
#include <stdio.h>

int recur_fibo(int n) {
    if (n <= 1)
        return n;
    else
        return(recur_fibo(n-1) + recur_fibo(n-2));
}

int main (int argc, char* argv[]) {
    int nterms = 1;
    for (int n = 0; n < nterms; n++) {
        printf("%d\n", recur_fibo(n));
    }
}
$ time (gcc  -Wall -o fibo fibo.c ; ./fibo)
0

real    0m0.205s
user    0m0.047s
sys     0m0.094s
Hmm.. About the same. Seems JS does very well on the "edit, run, debug" cycle. It gets even better as the programs get bigger and more complex.
Last edited by Heater on Sat Nov 03, 2018 1:14 am, edited 1 time in total.
Memory in C++ is a leaky abstraction .

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Fri Nov 02, 2018 7:11 pm

Your time did not include the C programs execution time. (time stops at the semi-colon).

Its different with the original 37 terms:
The C code.

Code: Select all

#include <stdio.h>

static int
recur_fibo( const int n )
{
  return n <= 1 ? n : recur_fibo(n-1) + recur_fibo(n-2);
}

int
main( void )
{
  for( int n = 0; n < 37; ++n )
    printf( "%d\n", recur_fibo(n) );
}
The new C interpreter!

Code: Select all

#!/bin/dash
gcc -O2 $1.c -o $1
./$1
The run ...

Code: Select all

$ time ./ccint fibo
0
1
1
.......snip.......
9227465
14930352

real	0m0.911s
user	0m0.845s
sys	0m0.066s
JS took

Code: Select all

$ time node fibo.js
0
1
1
.... snip ....
9227465
14930352

real	0m6.554s
user	0m6.469s
sys	0m0.090s
It would likely be the other way round with less terms.

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Fri Nov 02, 2018 8:00 pm

By the way, I looked at the assembler produced for the C version and its done some complex transformation that I don't understand.
But I can see that it has partially unrolled (if that's the word) the recursion. There is only one recursive call, not two in recur_fibo()!!!
The n-2 one seems to be pre-calculated somehow.
I think the compiler has cheated :(

Heater
Posts: 13592
Joined: Tue Jul 17, 2012 3:02 pm

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 1:53 am

jahboater,
Your time did not include the C programs execution time. (time stops at the semi-colon).
Oops..well spoted. I fixed it above. Soes not make much difference.


Interesting, on my PC with 37 iterations I get a closer race between JS and C "interpreter". Python is far behind.

Code: Select all

$ time python2  fibo.py
0
1
...
14930352

real    0m12.049s
user    0m11.891s
sys     0m0.063s

$ time node  fibo.js
0
1
...
14930352

real    0m0.752s
user    0m0.578s
sys     0m0.156s

$ time (gcc  -Os -Wall -o fibo fibo.c ; ./fibo)
0
1
...
14930352

real    0m0.447s
user    0m0.203s
sys     0m0.141s
I think the compiler has cheated
Ha! Yes. Interesting. I don't think I have seen GCC do that before.

I believe this is an example of "tail call" optimization. Basically, if the last thing a function does is to call itself then it may as well "goto" itself rather make a "call"

https://david.wragg.org/blog/2014/02/c- ... lls-1.html

Which has the interesting effect that code behavior then depends on optimization level. For example this recursive call is and endless loop with -O3 but crashes when it runs out of stack with -O0:

Code: Select all

$ cat tail.c
#include <stdio.h>

void recur() {
        recur();
}

int main (int argc, char* argv[]) {
        recur();
}
$ gcc -o tail -O3 tail.c
$ ./tail
^C
$ gcc -o tail -O0 tail.c
$ ./tail
Segmentation fault (core dumped)
Memory in C++ is a leaky abstraction .

User avatar
Paeryn
Posts: 2698
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 3:02 am

Heater wrote:
Sat Nov 03, 2018 1:53 am
I believe this is an example of "tail call" optimization. Basically, if the last thing a function does is to call itself then it may as well "goto" itself rather make a "call"
It's not tail recurrsion because the last thing the function does is to add two values from previous calls to itself. If I have time tomorrow I'll convert the optimised function back into C (I can see what part of it is doing but there is a lot of unrolled code).

Interestingly the for loop in main() doesn't call the function for the first two values, the compiler realises that it can just use constants for them (it doesn't pull those first two prints out of the loop though).
She who travels light — forgot something.

Heater
Posts: 13592
Joined: Tue Jul 17, 2012 3:02 pm

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 4:04 am

Strangely enough that is how I reasoned about tail-call optimization and the recursive fibo some years ago. At the time I decided it was not possible.

Looks like GCC disagrees!

Hope you can work out what GCC is doing there. That asm gives me headache.
Memory in C++ is a leaky abstraction .

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 8:19 am

I "suspect" that GCC has deduced the relationship between recur_fibo(n-1) and recur_fibo(n-2) and therefore doesn't need to call it a second time.
Its only my guess, as the asm gives me a headache too. GCC 7+ intersperses the original C source code with asm insns but its not making it clearer here.

BTW I changed it to an expression.

static int
recur_fibo( const int n )
{
return n <= 1 ? n : recur_fibo(n-1) + recur_fibo(n-2);
}

Heater
Posts: 13592
Joined: Tue Jul 17, 2012 3:02 pm

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 9:28 am

It's interesting to read about modern JS engines. Seems they are JIT compilers but they are sneaky about it. They don't have the type information that a Java compiler provides for it's JIT run times. For example they will interpret in a more normal fashion at startup. Then they will JIT functions on the fly after gathering information about parameter types etc as it runs, which they can use to optimize things. For example if a function always takes an integer parameter the code will be generated to handle ints rather than any float, string, object etc.

Of course JS is a very dynamic language so something that seems to always take an int may well get given a string at some point. Then the engine has to throw away the optimized JIT code and revert to regular interpretation.

So yes, top creds to the teams at Google, Firefox and Microsoft for getting JS to perform so well in recent years.

It's true that 15.9MB is shocking to us old timers. Don't forget though that if you are iterating on code development in C you also need GCC installed, which is huge, and a bunch of libraries. The JS runtime contains a mass of useful library modules: https://nodejs.org/dist/latest-v10.x/docs/api/. Besides 15.9MB hardly shows up as disk usage now a days.

Edit: jahboater seems to have deleted a couple of paragraphs I was replying to, so this post looks all out of context now.
Memory in C++ is a leaky abstraction .

gkreidl
Posts: 6108
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 9:33 am

The original topic was "big python numbers". It has degraded to a speed (and language) discussion.

Recursion is slow in Python. Using another algorithm, we can speed it up about 400000 times (for 36) - and we can also calculate really big fibonacci numbers.

Code: Select all

import time

def fibo2(n):
    farr = [1,1]
    for i in range(0,n-1):
        farr.append(farr[i]+farr[i+1])
    return farr

pos = 10000
t = time.time()
res = fibo2(pos-1)
dur = time.time()-t
print (res[-1])
print (dur)
It calculates the 10000th value of the fibonacci series and can be run in both python 2 and 3. It needs about 35 milliseconds (Python 2, Jessie).

Code: Select all

33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
0.0350520610809

Now try to do the same in other languages if you like.
Last edited by gkreidl on Sat Nov 03, 2018 9:58 am, edited 2 times in total.
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 9:51 am

Heater wrote:
Sat Nov 03, 2018 9:28 am
It's true that 15.9MB is shocking to us old timers. Don't forget though that if you are iterating on code development in C you also need GCC installed, which is huge, and a bunch of libraries. The JS runtime contains a mass of useful library modules: https://nodejs.org/dist/latest-v10.x/docs/api/. Besides 15.9MB hardly shows up as disk usage now a days.

Edit: jahboater seems to have deleted a couple of paragraphs I was replying to, so this post looks all out of context now.
Sorry, I didn't think I was contributing anything useful with that post.
Python appears to behave like a traditional interpreter.
All credit to Javascript that its even worth comparing it to a compiled language.

Yes, I don't care about the disk space either.
Its just that to run a JS program, up to 3828 blocks "might" be loaded from disk, compared to 2 blocks for the compiled program (fibo in C is 5KB).
Its also larger than Python which is 774 blocks for Python2 and 971 blocks for Python3.
I know the OS may not load everything in one go. But reading stuff off disk is a slow thing and best avoided.
The dash shell (23 blocks) is much faster than bash (223 blocks).
I guess if most JS programs are load once and run forever, then it doesn't matter at all.

I often use -Os, instead of -O3 for C because the program start time is faster than with the larger -O3 executable, even though the -O3 one may run faster once loaded.
Last edited by jahboater on Sat Nov 03, 2018 10:36 am, edited 1 time in total.

jahboater
Posts: 4759
Joined: Wed Feb 04, 2015 6:38 pm

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 9:58 am

gkreidl wrote:
Sat Nov 03, 2018 9:33 am
Now try to do the same in other languages if you like.
Yes. That is a good example of Python doing something well.
Its easy enough in C with GMP but its more messy and requires an external library, the Python code is part of the language and rather elegant.

Heater
Posts: 13592
Joined: Tue Jul 17, 2012 3:02 pm

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 1:00 pm

gkreidl,

OK, let's stick to big numbers, ... and some language debate...
Recursion is slow in Python. Using another algorithm, we can speed it up about 400000 times (for 36)...
You are right, the recursive fibo is not a sane way to calculate Fibonacci numbers. It's cute algorithm that basically only good for bench marking function call overhead.

The regular iterative approach is the fast way to get there. However your algorithm is terrible, it's creating a potentially very big array of potentially very big numbers.
- and we can also calculate really big fibonacci numbers.
Ah yes, Python's nuclear weapon, big integers. Certainly having language support for big numbers is very convenient for the programmer. And importantly it removes a whole class of bugs due to integer overflow. Unfortunately Python is not very good at big numbers. In fact it's terrible.

If we push this up to fibo(400001) your Python code takes about 20 seconds to get a result. Then takes 40 seconds cleaning up after itself having used all 8GB of my RAM. Probably because of the way you have implemented it.

Code: Select all

$ time python fibo.py
...
...
00223177808511231471431584086256462442917968655682697969250521391177719540915132752661447337501
20.819396019

real    0m54.720s
user    0m3.141s
sys     0m33.797s
Now try to do the same in other languages if you like.
Challenge accepted!

Using the bignum module in JS the fibo(400001) job is done in 3 seconds with a total run time of about 5 seconds. Without eating all my RAM.

Code: Select all

$ time node fibo.js
...
00223177808511231471431584086256462442917968655682697969250521391177719540915132752661447337501
2993ms

real    0m5.322s
user    0m3.484s
sys     0m1.781s
Here is the code:

Code: Select all

var bignum = require('bignum');

function fibo2 (n) {
    let f1 = bignum(1)
    let f2 = bignum(0)

    for (let i = 0; i < n; i += 1) {
        let f = f1.add(f2)
        f2 = f1
        f1 = f
    }
    return f2
}

n = 400001

let t = new Date()
let f = fibo2(n);
let dur = new Date() - t
console.log(f.toString())
console.log(dur + "ms")
From a mathematical point of view it would be better to use fibo2(pos-1), because we start counting with "1" and not zero
That seems to depend on which mathematician you speak to.

The famous and respected On-Line Encyclopedia of Integer Sequences defines the Fibonacci sequence as starting with 0, 1. https://oeis.org/A000045

F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1

So that is what I do.
Memory in C++ is a leaky abstraction .

gkreidl
Posts: 6108
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 2:00 pm

Never trust wikipedia :-) That's where I got the starting values 1,1 from, but most mathematical websites seem to use 0,1.

My algorithm returns the complete fibonacci series up to a limit. If you are only interested in one (last) value your algorithm is much better (faster and less memory usage). Of course you can also implement that in Python. And Python will always be slower than JIT compiled Javascript.
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer

Return to “Python”