Arbitrary precision integer math in BASIC

Discuss software for the Apple 1/replica 1

Arbitrary precision integer math in BASIC

Postby lorddoomicus » Sep Thu 25, 2008 10:48 pm

I've been playing around with the doing arbitrary precision math in basic. I figured out one way ( don't know if it's good or not ), that uses arrays. One limitation maybe entering in the numbers. Another, of course is memory.

I wrote a fibonacci calculator that finds fibonacci numbers out to 35 places ( up to the 173'rd number ). It runs pretty fast on dinaao on my MacBook, not so fast on a real Replica 1.

Still, I find that doing math to any precision under a limited environment an interesting problem.

Here is my program ( I'll put it on my Replica 1 page as well ):


Code: Select all
5 REM 1ST 173 FIBONACCI NUMBERS
10 M=172
20 N=36
30 DIM A(N)
40 DIM B(N)
50 DIM C(N)
60 K=0: X=1
70 FOR I=1 TO N
80 A(I)=0:B(I)=0:C(I)=0
90 NEXT I
100 B(N)=1
110 PRINT "0";: TAB 5
120 FOR I=1 TO N
130 PRINT A(I);
140 NEXT I
150 PRINT
160 PRINT "1";: TAB 5
170 FOR I=1 TO N
180 PRINT B(I);
190 NEXT I
200 PRINT
210 FOR I=1 TO M
220 X=X+1
230 PRINT X;: TAB 5
240 FOR J=N TO 1 STEP -1
250 Z=A(J)+B(J)+K
260 K=0:Y=Z/10
270 IF Y>0 THEN 500
290 C(J)=Z
300 NEXT J
310 FOR L=1 TO N
320 A(L)=B(L)
330 NEXT L
340 FOR L=1 TO N
350 B(L)=C(L)
360 NEXT L
370 FOR L=1 TO N
380 PRINT C(L);
390 NEXT L
400 PRINT
410 NEXT I
420 PRINT
430 END
500 K=Y
510 Z=Z-(10*Y)
520 GOTO 290


So, I have three arrays, all the same size, I take two and add them together in the third ( notice the adding loop goes backwards to keep the endian-ness matching the way we write numbers ). I have a carry variable, and logic to handle when there is a carry.

Like I said, I'm not sure how good it is ... but I think it is kinda clever. Just me trying to think like a computer.

- Derrik
Derrik Walker v2.0, RHCE
http://www.doomd.net
lorddoomicus
 
Posts: 32
Joined: Sep Thu 07, 2006 10:30 pm
Location: Mentor Ohio

Postby Kallikak » Sep Fri 26, 2008 2:36 am

You would find this thread interesting then.

http://www.brielcomputers.com/phpBB2/vi ... .php?t=327

One thing I'd suggest is to use base 100 in your arrays and convert to print. You could even use base 256 if you're prepared to work a bit harder on the conversion.

Ken
Kallikak
 
Posts: 172
Joined: Jan Sun 29, 2006 7:42 pm
Location: Sydney

Postby Kallikak » Sep Fri 26, 2008 2:37 am

Of course what I'd really recommend is writing it in assembly. Would be quite straightforward since it only involves adding and carry. Just use the same approach, but the speed will be greatly enhanced.
Kallikak
 
Posts: 172
Joined: Jan Sun 29, 2006 7:42 pm
Location: Sydney


Return to Software

Who is online

Users browsing this forum: No registered users and 1 guest