Add two very big numbers

[altenbach · Accepted solution]

Here's a quick draft how you could use Base 1G instead of base 10 to calculate the N'th Fibonacci number.

See what speed you get (on my very (very!!) old laptop, its about 40s for 1M.)

... and yes, there are probably much faster ways to do all that..... 😄

[nitad54449]

Hi

Your new code gives the 1M value in 20 sec on my PC (as a vi, not compiled). Your previous version took 192 seconds for the same calculation (and my initial version took 400 sec).

So, one order of magnitude better !

Regards

[altenbach]

---

@nitad54449 wrote:

...(as a vi, not compiled).

---

LabVIEW is ALWAYS compiled (details), but I did disable debugging for a slight edge. When debugging is enabled, it adds some extra code to e.g. probe wires, etc.

Still, I think there is some slack left to tighten up, but I have not studied it in detail. For large N, this is turning into a relatively hard problem because the numbers are growing so fast.

Even if you only want a limited amount of significant digits, an EXT calculations runs out of range somewhere above N=20k and you get "Inf". You can see that the results agree with my earlier code for e.g. 20k. (mantissa and # of digits)

[nitad54449]

>Still, I think there is some slack left to tighten up, but I have not studied it in detail. For large N, this is turning into a relatively hard problem because the numbers are growing so fast.

Just for info : for the 10M number, it requires almost one our calculation, the number obtained has 2089877 characters (close to the number of characters in a big book; the Bible has 3M chars).

[nitad54449]

---

@nitad54449  a écrit :

>Still, I think there is some slack left to tighten up, but I have not studied it in detail. For large N, this is turning into a relatively hard problem because the numbers are growing so fast.

Just for info : for the 10M number, it requires almost one our calculation, the number obtained has 2089877 characters (close to the number of characters in a big book; the Bible has 3M chars).

---

almost one hour

[altenbach]

---

@nitad54449 wrote:
almost one hour

---

OK, that's still doable. Your original code would probably have taken a day or more 😄

[Yamaeda]

---

@altenbach wrote:

Here's a quick draft how you could use Base 1G instead of base 10 to calculate the N'th Fibonacci number.

See what speed you get (on my very (very!!) old laptop, its about 40s for 1M.)

---

I tried with switching to U64, but that was 2.5x slower!

[altenbach]

---

@Yamaeda wrote:
I tried with switching to U64, but that was 2.5x slower!

---

Yes, that has always been my experience. (but I did try here too, adjusting the base much higher, of course). It seems that 32bit integer operation are especially efficient. Not sure that it has to be this way...

[JÞB]

---

@altenbach wrote:

---

@Yamaeda wrote:
I tried with switching to U64, but that was 2.5x slower!

---

Yes, that has always been my experience. (but I did try here too, adjusting the base much higher, of course). It seems that 32bit integer operation are especially efficient. Not sure that it has to be this way...

---

My 8-Ball is suggesting that you have really found a underoptomized edge use case for an Off The Shelf OS / uP computer system.

Frankly, I am just plain impressed 😎

[nitad54449]

---

@altenbach  a écrit :

---

@nitad54449 wrote:
almost one hour

---

OK, that's still doable. Your original code would probably have taken a day or more 😄

---

I test it and it took 19 hours 🙂