Mintoris Forum

Author Topic: 15 digit integers  (Read 3149 times)

Laszlo

  • Full Member
  • ***
  • Posts: 34
15 digit integers
« on: Feb 08, 2011, 04:42 PM »
When we do experiments in number theory, even the simplest task, printing the products of 7-8 digit integers is not so simple.

The bitwise operations work on 32-bit signed numbers, as documented. Printing 1<<32 gives 1, 1<<34 gives 4, but 1<<31 is shown as a large negative number (the sign bit is set). They cannot be used for large integers. If we employ them on larger numbers, the result will be the largest positive or negative 32 bit integer, so not even the parity of the input can be determined.

Hex$() works well till 53 bit positive integers, properly rounding non-integer numbers
Bin$() works, too, but prepends up to 3 leading 0's to make the output length a multiple of 4. It also rounds fractional numbers.
These functions don't work nicely on negative numbers (some 11‥10 bits are prefixed to make the result 64 bit long, but the prefix is different in Hex$ and Bin$, and it also depends on the number).

Real (fractional) numbers are represented as standard (IEEE 754-1985) 64-bit doubles. They contain 52 bits fractional parts, with an implied 1 bit in front. It means, for numerical calculations we have 53 bit accuracy. The range covers more than 90% of all, at most 16 digit integer numbers (2^53 = 9007199254740992). We can verify that with

i = 2^52
j = i+1
If i=j Then Print "EQ"

Nothing is printed (DroidX), showing that these 53 bit integers are represented in the phone as different double precision floating point numbers. However, if the exponent is increased to 53 (i = 2^53), we find that i+1=i, that is, 54 bit numbers are rounded, not exact any more. We see this also when printing (k*k)%100 with k=2^27+1. The printed result is even (40), although the true value is odd. At k=2^26+1 the result is correctly odd (25).

Consequently, with care, we can do exact integer arithmetic if the intermediate results do not grow above 9007199254740991. At an overflow there is no danger of flipping the sign bit, only the least significant bits get lost, by rounding up or down.

To do 53 bit accurate calculations, we must have "Rounding Off", otherwise intermediate results could get truncated. Unfortunately, in this case large integers get printed in scientific notation (4.50360e+15). On the other hand, if we want to do calculations with large integers, we have to make sure the intermediate results don't get longer than 53 bits. To be safe, we'd better restrict the I/O range of our numbers to 15 decimal digits (<2^50). Inputting and printing 15 digit numbers seem to work, but we cannot print 16 digit numbers with the Print command: Print 2^52 shows 4503599627370500 (although 2^52 = 4503599627370496). The last digit is rounded, so some extra computation and string manipulation would be necessary.

FixDecimal 0 makes numbers printed in scientific notations, if they are more than 10 digits long, but without decimals, so this setting is not helpful.
FixDecimal 15 still makes large integers printed in scientific notations, but with 15 decimals, rounded.
Str$() has the same rounding and formatting as Print.

We need a function, which provides the exact string representation of large integers, when scientific notation is forced with FixDecimal 15,1. Here is a possible one, to be used as Print LI$(n):

Sub LI$(z)                              ' Long Integer output format
  s$ = Str$(abs(z))                     ' ASSUME: FixDecimal 15,1 (scientific notation)
  s$ = Left$(s$,1)+Right$(s$,Len(s$)-2) ' Remove chr2 (decimal point)
  n  = Val(Right$(s$,3))                ' exponent: +12
  If n < 0 Then return "0"
  If z < 0 Then return "-" + Left$(s$,n+1)
  return Left$(s$,n+1)
End Sub
« Last Edit: Feb 08, 2011, 04:59 PM by Laszlo »

Chuck

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1899
Re: 15 digit integers
« Reply #1 on: Apr 29, 2011, 10:04 AM »
Laszlo this is an outstanding analysis of the limits of Basic variables.

Chuck

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 1899
Re: 15 digit integers
« Reply #2 on: May 14, 2011, 12:09 AM »
There is a new function in the latest version of Basic which should simplify printing large numbers:

Rounding Off
Print Format$(2 ^ 50, "###############")

to pad a number with leading zeros use a asterisk-pad_char at the beginning of the format.

Print Format$(2, "*0###############")

or to pad with spaces use a asterisk-space.

Print Format$(2, "* ###############")

There is a Java class called BigDecimal which lets you work with any size number.  The drawback is that not many of the standard numeric functions are available for this class.  I would have to add BigDecimals as an object variable.  So the syntax sould look something like…

bdA = BigDecimal("some big number")
bdB = BigDecimal("some other big number")

bdC = BDMinus(bdA, bdB)

Numeric operation on BigDecimal object variables would be limited to plus, minus, multiply, divide, power, and square root.  Let me know if this would be of interest to anyone.

-Chuck


 

« Last Edit: May 14, 2011, 04:00 AM by Mintoris »