Text Only | Text with Attachments

QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: david_uwi on September 25, 2021, 04:19:42 am

Title: Possible error in INTEGER64 calculations
Post by: david_uwi on September 25, 2021, 04:19:42 am
Sorry I've not got the latest version, so if this has been sorted you can delete this.

DIM z AS _INTEGER64
z = 7 ^ 19
PRINT z

The answer should end in ..373143, but the above gives ...373144

Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 25, 2021, 12:54:33 pm
^ power is imprecise:
Code: QB64: [Select]
  2. z = 7 ^ 19
  4. z = 1
  5. For i = 1 To 19
  6.     z = z * 7
  9.  
  10.  
Title: Re: Possible error in INTEGER64 calculations
Post by: SMcNeill on September 25, 2021, 01:07:03 pm
This may be a case of intermediary math issues, where the program is storing theresults as the wrong type as it calculates the answer.

To explain what I’m speaking of, think of how that end result is PROCESSED.

z = 7 ^ 19

Somewhere in our math processors, the computer will take those two numbers (7 and 19) and then process them according to the operator between them…

z is an INTEGER64, as you’ve defined it, but what are 7 and 19??  I’m thinking they’re probably SINGLE values, since that’s what QB64 types are by default.  If so, what do you think the internal registers use to store the result of a SINGLE raised to a SINGLE? 

I’d imagine that intermediate step would store the math result in a SINGLE, and your end result is so large you lose perfect precision.

I’m not at a PC right now (and my ipad can’t compile QB64 programs), but see what the results look like if you specify 7 and 19 as INT64 values:

z = 7&& ^ 19&&

It may end up making a world of difference!
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 25, 2021, 01:17:54 pm
Nope it's ^ it uses formulas LOG or EXP with lots of digits to do ^ calcs, multiplying with * is more precise.
 
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 25, 2021, 01:26:56 pm
Quote from: bplus on September 25, 2021, 01:17:54 pm
Nope it's ^ it uses formulas LOG or EXP with lots of digits to do ^ calcs, multiplying with * is more precise.

The beauty of ^ is that you are not limited to integers.
Title: Re: Possible error in INTEGER64 calculations
Post by: david_uwi on September 25, 2021, 01:58:56 pm
Interesting. I will bear that in mind when using ^.
I note that 7^21 is even further out
..284007 is correct putting in 7^21 the number ends in ends in ..284032 (25 too big).
"casting" (as I believe it is called) 7&&^21&& gives the same value as 7^21.
Title: Re: Possible error in INTEGER64 calculations
Post by: random1 on September 28, 2021, 11:31:26 pm
I've ran into similar problems in dealing with very large numbers
but was never able to find a work-around.  Hope someone here
can help with a solution.
R1     
Title: Re: Possible error in INTEGER64 calculations
Post by: Pete on September 28, 2021, 11:50:22 pm
Another argument for String Math! I haven't done powers with it, but it would be as simple as a multiplication loop. I'm not sure if poers has any tricks, like finding square roots. Anyway, anything _INTEGER64 can do String Math can do better.

Pete
Title: Re: Possible error in INTEGER64 calculations
Post by: david_uwi on September 29, 2021, 03:10:23 am
It certainly could catch out the unaware.
That said it is integer arithmetic - both arguments 7 and 21 are integer so the answer is integer.
As long as there are no overflows it is reasonable to assume that the integer answer should be the correct answer, but it is not.

The compiler should not default to floats when doing integer calculations (but what do I know I've never tried to write a compiler so I have no clue as to the difficulties)
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 29, 2021, 01:44:57 pm
The way I think of ^ is like /, you use it then you have lost pure integer returns from the operator.

^ still very good up to 14 digits.

@david_uwi  you could setup your own Power&& function to be assured integers (or error flag).
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 29, 2021, 02:11:36 pm
something like this
Code: QB64: [Select]
  2.     'take x to an integer power
  3.     Dim As _Integer64 z, y
  5.     y = x
  6.     n = e
  7.     z = 1&&
  8.     While n > 0
  9.         While (n Mod 2) = 0
  10.             n = n \ 2
  11.             y = y * y
  12.         Wend
  13.         n = n - 1
  14.         z = y * z
  15.     Wend
  16.     ipower = z
  18.  
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 29, 2021, 02:16:17 pm
you could also substitute WHILE (n MOD 2) = 0 with While (n And 1) = 0 which might be faster
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 29, 2021, 02:19:37 pm
I wonder why the middle stuff?
Code: QB64: [Select]
  1. Print ipower&&(7, 21)
  2.  
  4.     'take x to an integer power
  5.     Dim As _Integer64 z, y
  7.     y = x
  8.     n = e
  9.     z = 1&&
  10.     While n > 0
  11.         'While (n Mod 2) = 0  ' why have this?
  12.         '    n = n \ 2
  13.         '    y = y * y
  14.         'Wend
  15.         n = n - 1
  16.         z = y * z
  17.     Wend
  18.     ipower = z
  20.  
  21.  
  22.  

Seems to work for the one sample I tested. ;-))

Good to make copies of arguments and use a While loop as opposed to For.
Title: Re: Possible error in INTEGER64 calculations
Post by: SMcNeill on September 29, 2021, 02:25:27 pm
*Bplus — half the loops.

3 ^ 12 = 3*3*3*3*3*3*3*3*3*3*3
9 ^ 6 = (3*3)*(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
81 ^ 3 = you get the point.  :P
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 29, 2021, 02:30:56 pm
Oh so if e where a power of 2, then only one outer loop, clever!

Code: QB64: [Select]
  1. Print ipower&&(7, 16)
  2.  
  4.     'take x to an integer power
  5.     Dim As _Integer64 z, y
  7.     y = x
  8.     n = e
  9.     z = 1&&
  10.     While n > 0
  11.         outer = outer + 1
  12.         While (n Mod 2) = 0 ' why have this?
  13.             inner = inner + 1
  14.             n = n \ 2
  15.             y = y * y
  16.         Wend
  17.         n = n - 1
  18.         z = y * z
  19.     Wend
  20.     ipower = z
  21.     Print outer, inner
  23.  
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 29, 2021, 02:37:12 pm
Need error flag for this:
Code: QB64: [Select]
  1. Print ipower&&(7, 32)
  2.  
  4.     'take x to an integer power
  5.     Dim As _Integer64 z, y
  7.     y = x
  8.     n = e
  9.     z = 1&&
  10.     While n > 0
  11.         outer = outer + 1
  12.         While (n Mod 2) = 0 ' why have this?
  13.             inner = inner + 1
  14.             n = n \ 2
  15.             y = y * y
  16.         Wend
  17.         n = n - 1
  18.         z = y * z
  19.     Wend
  20.     ipower = z
  21.     Print outer, inner
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 29, 2021, 03:46:16 pm
Quote from: bplus on September 29, 2021, 02:37:12 pm
        While (n Mod 2) = 0 ' why have this?
while n is even
    divide n by 2 and square the result
wend
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 29, 2021, 04:18:22 pm
Thanks @jack

Steve got here first to explain, clever idea!

We need error checking for when numbers get too big.
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 30, 2021, 08:27:01 am
bplus, can you think of an easy and efficient way to detect or prevent overflow?
there might be some ideas from this post https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c
Title: Re: Possible error in INTEGER64 calculations
Post by: SMcNeill on September 30, 2021, 09:18:11 am
Quote from: jack on September 30, 2021, 08:27:01 am
bplus, can you think of an easy and efficient way to detect or prevent overflow?
there might be some ideas from this post https://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c

Precalculate values with _FLOATs.  If the result is greater than what an INT64 can hold, flag an error and reject them.
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 30, 2021, 10:07:56 am
never mind, it didn't work
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 30, 2021, 10:09:47 am
Quote from: SMcNeill on September 30, 2021, 09:18:11 am
Precalculate values with _FLOATs.  If the result is greater than what an INT64 can hold, flag an error and reject them.

I had similar thought getting out of bed this morning. The b ^ e = Exp(e * Log(b)) may fail in precision before the limit of _Integer64 though. Will be interesting challenge to test.

(Jack just posted as I was editing this. So I have yet to study your reply jack.)

wait... what am I thinking?  the precision for the calc using * will be fine as long as we don't go over.
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 30, 2021, 10:17:55 am
bplus, when I tested with x=2 it seemed to work but it doesn't work for other numbers
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 30, 2021, 11:41:45 am
bplus, this should work, it's up to the user to decide what to do when overflow occured
reference https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
Code: QB64: [Select]
  2.     Function mul_overflow& Alias "__builtin_smulll_overflow" (ByVal a As _Integer64, Byval b As _Integer64, res As _Integer64)
  4.  
  5. 'Print ipower(2&&, 3)
  6. 'Print ipower(2&&, 4)
  7. 'Print ipower(2&&, 5)
  8. Print ipower(3&&, 40)
  9.  
  11.     'take x to an integer power
  12.     Dim As _Integer64 z, y
  14.     Dim As Long f
  15.     y = x
  16.     n = e
  17.     z = 1&&
  18.     While n > 0
  19.         While (n And 1) = 0
  20.             n = n \ 2
  21.             f = mul_overflow(y, y, y) 'y = y * y
  22.             If f Then Print "an overflow occured"
  23.         Wend
  24.         n = n - 1
  25.         f = mul_overflow(y, z, z) ' z = y * z
  26.         If f Then Print "an overflow occured"
  27.     Wend
  28.     ipower = z
  30.  
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 30, 2021, 12:18:31 pm
a little better
Code: QB64: [Select]
  1. ' reference https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
  3.     Function mul_overflow& Alias "__builtin_smulll_overflow" (ByVal a As _Integer64, Byval b As _Integer64, res As _Integer64)
  5.  
  6. Print ipower(3&&, 39)
  7. Print ipower(3&&, 40)
  8.  
  10.     'take x to an integer power
  11.     Dim As _Integer64 z, y
  13.  
  14.     y = x
  15.     n = e
  16.     z = 1&&
  17.     While n > 0
  18.         While (n And 1) = 0
  19.             n = n \ 2
  20.             If mul_overflow(y, y, y) Then Print "an overflow occured"
  21.         Wend
  22.         n = n - 1
  23.         If mul_overflow(y, z, z) Then Print "an overflow occured"
  24.     Wend
  25.     ipower = z
  27.  
Title: Re: Possible error in INTEGER64 calculations
Post by: jack on September 30, 2021, 12:33:22 pm
hello everyone, why didn't you think of the obvious simple solution?
a positive integer that overflows will be negative
never mind, that doesn't always work
Title: Re: Possible error in INTEGER64 calculations
Post by: bplus on September 30, 2021, 12:52:24 pm
Quote
hello everyone, why didn't you think of the obvious simple solution?
a positive integer that overflows will be negative

But only for a little while then it builds up to positive number again, just wrong and way too small!

This https://www.qb64.org/forum/index.php?topic=4210.msg135991#msg135991
shows positive result only it's wrong.

Is it possible numbers could slip through negative detection while calculating result?

@jack your built-in detector of overflow (in C++ ?) may be the better.
Title: Re: Possible error in INTEGER64 calculations
Post by: Pete on September 30, 2021, 11:39:39 pm
String math
How'd you get so funky
String Math
Can you use a hot key
String Math
Made by an Egyptian
String Math
Even does division
Born in Windows 7
Works in Win-11
String Math
Title: Re: Possible error in INTEGER64 calculations
Post by: Richard on October 29, 2021, 12:03:02 pm
@david_uwi


https://www.qb64.org/forum/index.php?topic=2276.msg137521#msg137521 (https://www.qb64.org/forum/index.php?topic=2276.msg137521#msg137521)  Reply #183


You may be interested in reading the above reply as it addresses the problem you are having. 

Note that there is a difference between "Overflow/Overrange" and "Numbers not representable".
Text Only | Text with Attachments