Re: [libtom] Abridged summary of libtom@googlegroups.com - 1 update in 1 topic

[Larry Bugbee]

On Jul 15, 2015, Ron Aaron wrote:

Attached is a small sample program which I've compiled against a 32-bit and a 64-bit version of TFM.  Both versions of TFM were compiled with FP_MAX_SIZE of 8192 instead of 4096.

The 64-bit version works as expected, the 32-bit gives an incorrect value (for 989 factorial); I would expect to get the same results from either.

Is there something I'm doing wrong in the TFM configuration?  I see this on all platforms (Windows, Linux, OS X)

N.B.: is there a way to detect overflow in TFM?

Thanks!

----------------------

I did not verify your code.  Nevertheless, a quick excursion with Python suggests 989! is a number 8420 bits in length.  Because you set FP_MAX_SIZE to 8192, I'm not surprised your 32-bit version did not return a correct answer.  

Python 2.7.10 (v2.7.10:15c95b7d81dc, May 23 2015, 09:33:12) 

[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin

Type "help", "copyright", "credits" or "license" for more information.

>>> 

>>> 

>>> 

>>> def fact(n):

...     if n == 1: return 1

...     return n * fact(n-1)

... 

>>> fact(3)

6

>>> fact(4)

24

>>> fact(5)

120

>>> f989 = fact(989)

>>> 

>>> from numutils import num2hex

>>> f989h = num2hex(f989)

>>> f989h

'e75c85d3df0a5c187ae530f5f72f154a8a52be3560af912ffd4f715c8bbd554cf24e72a8853dd89ad3149fc544f161b6fa2f57bd3cad86e0b620e6cce72617ff9a8eb92aca2dc63391951dd98f3df0f3c2ba8988afbfd252e3b15aa1c3793e44bd50fc62e304dfcb9aa06e2bc1abaa22b34eddb8d8e7bf7704342484f7e283a79dc9c174ded911eb14f8483a622ca31b1e4d62cc32bc1f695c5e1afa8ffdf938dabab99a9d7629ceaaf3164a2978e60f152c230afab4a0fbb0d1555f76acfce0e06fa7cf6cbb98ce679eda0ebc6c1ca7b7c0883fa0dbf98c3884c45a25256dcb4123ecbfa67c47842ec429e949902a5d67b806758c1d478baeb9d4f2b529f609becd32e784b177dd8eea91784ace51ab4378e9e4999d6c4c2d654040aeaebbacd9110784008a2cb2dffd1b82d669b214e539a08f683393a08cb05ac4fcc1fd88931a39a516d7501188bbc372a67befc470912db64b034e601bccf06d77074cdefd85230505c59e854a418079ba7f00d197c6e1d1efd845a32815a3205cbb4ced3dec5a4a5446f698c5350551ec31fd0e5182126cc8d3c2d844228e742937f5afc6fff733bcaebdd69dd602d8cdb46449a43e6e7e1c02190d6d897991120fd987b2d66fb8bd1218f2f8b0f9a7e25cb5af5ba91c568a3b96d31d9a60406e3d8f99af50c09f80d91e336293d7c04e12b81e27adb713207c117db5899c33170b216acab72dc32029453f80f91aead1f455479c26c46c7795b8ba7abd539060afbeb9186922365ec698fe6a9a4622fb451d20afa7d85523297162a44cfb798b5315fb43c6ab051e3cb980d00441e04f3e34565da8d51fe4a4615526dfc7dda030c40300a530a0a197c09abe13cc057d554185fe2f2783f277f7ed85ddeeb5b1f099f336fa8f2e7c69f54bc5341dece76656af73b680aece7df25e0b1f2d7dd7793f42f55cfd2e88e663b4cecdba719c6cade5a189d5d0000803040e69ea0411749e242271a928c49f5960f0ff7aaeeb2f9aa9fd95ea3b421f469974fafdd6d37309926c84ccd15e60f423d8a4e6cd506a0d4aef521546d157387478df678eccd84375e3470e0d223adb38d17c29a25390e4a1a7bd44d2c97d4c14fe6fa9d07f7555e3b2db0921d786fc3dcbad34b6958986ea17532b0fcb848f67c7937d31d8d6537b6186f738775674d8dcc22525ba5c3a448cc73a186988c8dd2477b886eb1b82b035d0d2f8ac8e9e1771f57eddba716da8c88e2d69666b3b5f5d74d5dac7e83cb73fa28502dc1193126e55dba9c7d5f8ba00a14e9b1741340efd527fec5a08ff69d5e200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'

>>> 

>>> len(f989h)*4        # 4 bits per nibble

8420

>>> 

How did you determine your 64-bit versions all gave the correct answer?  Were they all the same or did you compare against an independent calculation?  If correct, your 64-bit version perhaps provided the right answer for the wrong reasons.  There being extra workspace provided by extra high-order bits in each word might have been sufficient in the 64-bit version, but not so in the 32-.  

As for a way to test for high-order overflow, I am not aware of one in TFM.  It was designed with minimum overhead so it could be as fast as practicable on problems of a known maximum size.  For open-ended problems I suggest you generously oversize TFM and choose a lesser threshold against which you will test intermediate values.  Sans your threshold testing, super-sizing will likely not produce a time penalty, only a space penalty.  And be sure to carefully study your results.  

.

[Ron Aaron]

Hi.  The code verified by performing fact(989) / fact(988) and getting 989 as the answer.  Perhaps that's not the best verification, but it reflects a bug which was reported against our product using TFM.   I also just now checked it against the python code, and it works at least until fact(999) (after that python crashes).

I would have thought that the TFM code would work precisely the same on 32 and 64 -- either fail or succeed on 989!   The inability to capture overflow errors is something I'll have to give thought to.  I suppose your solution will work, e.g. make sure the highest spot stays zero, and complain if it changes from that.  At least that's a feasible solution, thanks.

[Larry Bugbee]

LOL!  Indeed, fact(999) worked but my Python raised an exception on fact(1000) because recursion limit was exceeded.  ...but not because it couldn't handle the size of the number.  I've used Python to operate on numbers above 15K bits, RSA-15520 et al.  But back to the problem at hand...

You are using 989! as a test case against your bug, but 989! exceeds the max size so an error shouldn't come as a surprise.  What happens if you super-size TFM (both the 64- and 32-bit versions) and try that against your original problem?  Will it crash then? 

[Ron Aaron]

Indeed: setting max to 10000 works for both 32 and 64 bit, so there's an *issue* where the 64-bit code allows bigger values than it should.  So it's in fact a 64-bit bug, not a 32-bit bug :o

I'll take this into account and add a simple overflow check now.  Thanks! 

[Larry Bugbee]

Whoa!!!  The issue has moved over to the 64-bit version?  Verrry interesting.  ???

Do you have a sense the problem is with your program and what it is trying to do, or that there is still a bug in TFM?   Have you tried using LibTomMath as a sanity check?

[Ron Aaron]

No, what I mean is that the 32-bit is correctly complaining about the number being too large, e.g. 989!.  The 64-bit just lets it fly, and gets the correct answer *but it shouldn't* 

[Larry Bugbee]

Interesting.

Right now I have two problems.  First it is waaaay past my bedtime and I'm beginning to fall asleep.  ...and second, I won't have much time to pursue it for the next few days at least, so may I suggest you recap your findings in a fresh problem statement.  Parsing long threads can get confusing making a clean, clear statement of what we now know will be appreciated by all.  Thanks Aaron.

[Ron Aaron]

On Monday, August 3, 2015 at 2:19:10 PM UTC+3, Larry Bugbee wrote:

Interesting.

Right now I have two problems.  First it is waaaay past my bedtime and I'm beginning to fall asleep.  ...and second, I won't have much time to pursue it for the next few days at least, so may I suggest you recap your findings in a fresh problem statement.  Parsing long threads can get confusing making a clean, clear statement of what we now know will be appreciated by all.  Thanks Aaron.

Sure. I'll take a whack at my issues.

Thanks for the assist.