large integers and strange(for me at least) behaviour

Anything Sinclair ZX Basic related; history, development, tips - differences between BASIC on the ZX80 and ZX81
bola_dor
Posts: 357
Joined: Wed Oct 02, 2019 5:32 am

large integers and strange(for me at least) behaviour

Post by bola_dor »

I was interested in the "Collatz conjecture" https://en.wikipedia.org/wiki/Collatz_conjecture and wanted to test how far zeddy could handle large integers. I expected it to return an error for an out-of-range integers but instead it returned wrong results by wrongly deciding whether a number is odd or even using the formula A/2<>INT(A/2).
The strange thing is that if I try to replicate the calculation error once the program is stopped it doesn't reproduce (?!)

first i wrote a simple code to perform the sequence from an INPUT A and count how many iterations did it take to reach the result A=1, it looked Ok but i wanted to test it I used the values that give the largest number of iterations from the chart in the wiki :

The starting value having the largest total stopping time while being
less than 10 is 9, which has 19 steps,
less than 100 is 97, which has 118 steps,
less than 1000 is 871, which has 178 steps,
less than 10^4 is 6171, which has 261 steps,
less than 10^5 is 77031, which has 350 steps,
less than 10^6 is 837799, which has 524 steps,
less than 10^7 is 8400511, which has 685 steps,
less than 10^8 is 63728127, which has 949 steps,
less than 10^9 is 670617279, which has 986 steps,
less than 10^10 is 9780657630, which has 1132 steps,[11]
less than 10^11 is 75128138247, which has 1228 steps,
less than 10^12 is 989345275647, which has 1348 steps,
less than 10^13 is 7887663552367, which has 1563 steps,
less than 10^14 is 80867137596217, which has 1662 steps,
less than 10^15 is 942488749153153, which has 1862 steps,
less than 10^16 is 7579309213675935, which has 1958 steps,
less than 10^17 is 93571393692802302, which has 2091 steps and
less than 10^18 is 931386509544713451, which has 2283 steps.

just to find the result corresponding to 8400511, which has 685 steps was not correct. then I added the lines to print "P" or "I" bellow the intermediate results according they were even(P) or odd(I), and check the result of the function storing the inicial value in B and comparing it when reverting the function in lines 106 and 126 leading to a STOP at that point.

20 LET C=-1
30 INPUT A
45 SCROLL
50 LET C=C+1
60 IF A=1 THEN GOTO 140
70 PRINT A
75 SCROLL
90 IF A/2=INT (A/2) THEN GOTO 120
95 PRINT "I"
100 LET B=A
105 LET A=(A*3)+1
106 IF (A-1)/3<>B THEN STOP
110 GOTO 40
120 LET B=A
121 PRINT "P"
125 LET A=A/2
126 IF A*2<>B THEN STOP
130 GOTO 40
140 PRINT ,C;" ITERACIONES"
160 RUN


on the zeddy it aparently takes the wrong desition aobout beng odd for an even number and then inverting the funtion and comparing to B leads to STOP.
then I tried on the Spectrum, it fails on the same entry but sooner on the iterations...
20 LET C=-1
30 INPUT A
44 POKE 23692,2
50 LET C=C+1
60 IF A=1 THEN GO TO 140
70 PRINT A
72 POKE 23692,2
90 IF A/2=INT (A/2) THEN GO TO 120
95 PRINT "I"
100 LET B=A
105 LET A=(A*3)+1
106 IF (A-1)/3<>B THEN STOP
110 GO TO 40
120 LET B=A
121 PRINT "P"
125 LET A=A/2
126 IF A*2<>B THEN STOP
130 GO TO 40
140 PRINT ,C;" ITERACIONES"
160 GO TO 1


my concern is that I got an erroneous result and not an error message.
How to handle it is a different matter as well.
Last edited by 1024MAK on Sun Oct 03, 2021 5:49 pm, edited 1 time in total.
Reason: Edited to add the raise to the power symbol to the numbers.
Ernesto
ZX80, TK83, CZ1000, CZ1500, TK85, CZ2000, CZ1000Plus, CZ1500Plus, CZ Spectrum, TK90X, CZ Spectrum Plus, ZX Spectrum, ZX Spectrum+, ZX Spectrum +2, Sinclair QL. And more to come :D
User avatar
1024MAK
Posts: 3916
Joined: Mon Sep 26, 2011 10:56 am
Location: Looking forward to summer in Somerset, UK...

Re: large integers and strange(for me at least) behaviour

Post by 1024MAK »

As both the ZX81 and the ZX Spectrum internally hold numbers in variables as floating point numbers, rounding errors often cause problems when using the equals compare and other similar constructs.

So although a number may appear to be an integral whole number, and the machine may even print it as such, internally it may have a factional part, and then A/2=INT(A/2) or A/2<>INT(A/2) may give a misleading result.

By the way, which ZX81 ROM version are you using?

Mark
Moggy
Posts: 2555
Joined: Wed Jun 18, 2008 2:00 pm

Re: large integers and strange(for me at least) behaviour

Post by Moggy »

Your chart looks confusing as for some reason the powers some of the numbers have to be raised to seems to have become part of the number itself.

EG . less than 10^4 is showing as..less than 104 is 6171, which has 261 steps,

Also your example... ( less than 10^7 is 8400511, which has 685 steps),has numbers > 8 digits in its calculations so is at the end of the ZX81's scope calculation wise and the following number. (less than 10^8 is 63728127, which has 949 steps,) is definitely outside the ZX81's capabilities without resorting to custom maths routines.


I came across this with the Collatz conjecture a long time ago, large numbers being my thing with the 81,and ended up resorting to FORTH which besides using it's own maths routines and being faster has the added bonus of working with higher integers than Sinclair BASIC.

Maths guru Dr Frank O'Hara wrote a couple of articles in ZX computing magazine pointing out the fallibility of the ZX81's floating point capabilities regardless of which version of the ROM used.
One of which was a rounding error concerning the 32nd bit of any calculation, also he showed how some numbers are held quite accurately whilst others are in error. He also showed a few workarounds for such situations.

As a bit of trivia he confirmed on a ZX81 in a run of around three hours what a Cray Mk1 took months to find back in 1976, that is find the highest prime number.
bola_dor
Posts: 357
Joined: Wed Oct 02, 2019 5:32 am

Re: large integers and strange(for me at least) behaviour

Post by bola_dor »

1024MAK wrote: Sun Oct 03, 2021 12:53 pm By the way, which ZX81 ROM version are you using?

Mark
I've made this with eighty-one, both ZX81 and Spectrum with the standard rom loaded by the emulator.
Both failed with same entry but at different progression level, Spectrum failed earlier :roll:


Moggy wrote: Sun Oct 03, 2021 1:32 pm Your chart looks confusing as for some reason the powers some of the numbers have to be raised to seems to have become part of the number itself.
The chart was copied from the Wikipedia cited earlier
Moggy wrote: Sun Oct 03, 2021 1:32 pm EG . less than 10^4 is showing as..less than 104 is 6171, which has 261 steps,

Also your example... ( less than 10^7 is 8400511, which has 685 steps),being an 8 digit number is at the end of the ZX81's scope calculation wise and the following number. less than 10^8 is 63728127, which has 949 steps, is definitely outside the ZX81's capabilities without resorting to custom maths roiutines.
I found out that chart as a way to test the program, and didn't question it.
Results are as expected including 10'6 example result..
Moggy wrote: Sun Oct 03, 2021 1:32 pm
I came across this with the Collatz conjecture a long time ago, large numbers being my thing with the 81,and ended up resorting to FORTH which besides using it's own maths routines and being faster has the added bonus of working with higher integers than Sinclair BASIC.
I suspected something like this should happen, but I spected an error message rather than an erroneous result, I've learned something.
Trying to solve this is beyond my actual capabilities. Perhaps z88dk if it has any sort of Linteger library..
I am just curious about math and ZX81 but not an expert in any way...
Moggy wrote: Sun Oct 03, 2021 1:32 pm Maths guru Dr Frank O'Hara wrote a couple of articles in ZX computing magazine pointing out the fallibility of the ZX81's floating point capabilities regardless of which version of the ROM used.
One of which was a rounding error concerning the 32nd bit of any calculation, also he showed how some numbers are held quite accurately whilst others are in error. He also showed a few workarounds for such situations.
I'd like to read that, is it online?

Moggy wrote: Sun Oct 03, 2021 1:32 pm As a bit of trivia he confirmed on a ZX81 in a run of around three hours what a Cray Mk1 took months to find back in 1976, that is find the highest prime number.
Amazing!!!
Ernesto
ZX80, TK83, CZ1000, CZ1500, TK85, CZ2000, CZ1000Plus, CZ1500Plus, CZ Spectrum, TK90X, CZ Spectrum Plus, ZX Spectrum, ZX Spectrum+, ZX Spectrum +2, Sinclair QL. And more to come :D
Moggy
Posts: 2555
Joined: Wed Jun 18, 2008 2:00 pm

Re: large integers and strange(for me at least) behaviour

Post by Moggy »

I should have condensed what I meant to say as the numbers involved in the calculations exceed the what the ZX81 can handle so it does its rounding on the digits it can display

Example

Using 8400511.

At one point point in the calculation the ZX81 produces the following...

828604480

414302240

124906700 (note the end zeros instead of an actual number due to the 81's limit being exceeded)

621453360..

And so on whereas the actual figures should be..

828604478

414302239

1242906718

621453359


You wont get any errors as the results are accurate within the magnitude of the numbers the ZX81 can work with and anything over 8 digits just gets zeros added on at the end and at one point if the result is large enough may even give the result in E notation however if the calculation involved something of the magnitude of 16^32 then you would get error 6 (mathematical overflow)


The magazine articles have been listed a few times here I will find the links and edit the post.


EDIT


My post near the end of this thread has the three links.

viewtopic.php?f=7&t=2153&p=23244&hilit= ... ara#p23244
Last edited by Moggy on Sun Oct 03, 2021 4:35 pm, edited 1 time in total.
bola_dor
Posts: 357
Joined: Wed Oct 02, 2019 5:32 am

Re: large integers and strange(for me at least) behaviour

Post by bola_dor »

Moggy, wonderful explanation.
Of course losing les significant to 0 rounds them to an even number decreasing the next step and completely changing the result.

On the spectrum I saw results expressed as E notation... and failed earlier BTW :D
I really appreciate your time and teaching here.
Ernesto
ZX80, TK83, CZ1000, CZ1500, TK85, CZ2000, CZ1000Plus, CZ1500Plus, CZ Spectrum, TK90X, CZ Spectrum Plus, ZX Spectrum, ZX Spectrum+, ZX Spectrum +2, Sinclair QL. And more to come :D
Moggy
Posts: 2555
Joined: Wed Jun 18, 2008 2:00 pm

Re: large integers and strange(for me at least) behaviour

Post by Moggy »

Always happy to help where I can Ernesto. :D

I have edited my last post to include the magazine links.
User avatar
1024MAK
Posts: 3916
Joined: Mon Sep 26, 2011 10:56 am
Location: Looking forward to summer in Somerset, UK...

Re: large integers and strange(for me at least) behaviour

Post by 1024MAK »

Just because…

Here’s the results from an Acorn BBC Master Compact:-
EF911FCC-E6FA-401B-95D3-9FB55490B32B.jpeg
First number is just a loop count. Second number is the start value. Third number is the number of steps.

As you can see, it failed the test at either line 106 or 126 (instead of STOP I jumped to a routine to print out the results).

Mark
User avatar
1024MAK
Posts: 3916
Joined: Mon Sep 26, 2011 10:56 am
Location: Looking forward to summer in Somerset, UK...

Re: large integers and strange(for me at least) behaviour

Post by 1024MAK »

For the ZX Spectrum, have a read of chapter 7 in its manual (link).
Manual wrote: Numbers are held to about nine and a half digits accuracy, so 1 e10 is too big to be held exactly right. The inaccuracy (actually about 2) is more than 1, so the numbers 1e10 and 1e10+1 appear to the computer to be equal. For an even more peculiar example, type
PRINT 5e9+1-5e9

Here the inaccuracy in 5e9 is only about 1, and the 1 to be added on in fact gets rounded up to 2. The numbers 5e9+1 and 5e9+2 appear to the computer to be equal.

The largest integer (whole number) that can be held completely accurately is 1 less than 32 2's multiplied together (or 4,294,967,295).
Mark
bola_dor
Posts: 357
Joined: Wed Oct 02, 2019 5:32 am

Re: large integers and strange(for me at least) behaviour

Post by bola_dor »

1024MAK wrote: Sun Oct 03, 2021 5:33 pm Just because…

Here’s the results from an Acorn BBC Master Compact:-
EF911FCC-E6FA-401B-95D3-9FB55490B32B.jpeg
First number is just a loop count. Second number is the start value. Third number is the number of steps.

As you can see, it failed the test at either line 106 or 126 (instead of STOP I jumped to a routine to print out the results).

Mark
Awesome!!! it fails at the same 8400511 entry.. did you check how many iterations runs until it fails?
Ernesto
ZX80, TK83, CZ1000, CZ1500, TK85, CZ2000, CZ1000Plus, CZ1500Plus, CZ Spectrum, TK90X, CZ Spectrum Plus, ZX Spectrum, ZX Spectrum+, ZX Spectrum +2, Sinclair QL. And more to come :D
Post Reply