Big Integer Library

Discussions related to the code libraries supplied with BB4W & BBCSDL
Post Reply
p_m21987
Posts: 122
Joined: Mon 02 Apr 2018, 21:51

Big Integer Library

Post by p_m21987 » Sun 12 May 2019, 15:22

Richard Russell has made this post on the raspberry pi forum. I thought it would be appropriate to cross post it here.

https://www.raspberrypi.org/forums/view ... 8#p1466828
Richard Russell wrote: Re: Introduction to BBC BASIC
Sun May 12, 2019 11:08 am

I mentioned in the other thread that I was thinking of writing a native code BigInt library for BBC BASIC; it would be an interesting exercise and hopefully provide a route to an efficient solution of the Fibonacci challenge. I've started to look at this, but I'm facing a dilemma: should I use a 10^n radix for the limbs (as the classic BASIC Fibo program does) or a more conventional 2^n radix? The advantage of the former is that the conversion back from the BigInt to decimal becomes trivial (and fast) which is of particular value when outputting a million-digit result! The disadvantage - and it's a big one - is that the BigInt computations themselves become significantly less efficient.

For a general-purpose BigInt library I'm in little doubt that the 2^n limb radix is better. In a typical application the formatting of the output as a decimal number is likely to be a small proportion of the total work (it might not even always be needed, if the output value isn't intended for 'human consumption') and efficiency of the BigInt arithmetic will be the most important factor (GMP uses a 2^n radix incidentally). But I suspect that in the specific case of the million-digit Fibonacci challenge it would give poor results because of the time taken to convert the result to decimal (which I assume is supposed to be part of the challenge).

What to do?! Does anybody have some BASIC code for multiple-precision binary-to-decimal conversion that I could benchmark?

Post Reply