Big Integer Library

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

Big Integer Library

Post by p_m21987 »

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?
DDRM

Re: Big Integer Library

Post by DDRM »

To follow up on this, Richard has made substantial progress in developing a limited BigInt library, and would value input from others to extend it. I copy, with permission, his comments to me:

Things have moved on since then: I've written a barebones library with sufficient functionality to solve the Fibonacci challenge, meaning only unsigned integers and just add, subtract and multiply operations (increment and decrement added today). I'm not particularly motivated to extend it to become a general purpose bigint library, by the addition of signed numbers and division etc., hence my desire to find out whether somebody else might want to take it on.

Anyone interested? As far as I'm aware the current code isn't available, but if you contact Richard privately he will presumably be happy to share it as a foundation for collaboration - hopefully he will release it anyway - it is clearly already useful in some contexts!

Best wishes,

D
User avatar
hellomike
Posts: 184
Joined: Sat 09 Jun 2018, 09:47
Location: Amsterdam

Re: Big Integer Library

Post by hellomike »

I sincerely hope that Richard will make it available for BB4W 6.x as well.
DDRM

Re: Big Integer Library

Post by DDRM »

As far as I understand, it is written purely in BBC BASIC, so it should run fine with BB4W. That also makes it more accessible to anyone wanting to help out, since I suspect that there are a limited number of us (not including me!) who might be able to write the routines in assembler...

Best wishes,

D