## Calculating digits of Pi in Basic

bbc/electron apps, languages, utils, educational progs, demos + more
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Calculating digits of Pi in Basic

Valentin Albillo, ingenious programmer of HP and Sharp calculators, offers a Pi-calculating program in just 7 lines of Basic, in this PDF as seen on his web site (where there are many other interesting works).

Here's his program, for a Sharp pocket computer:

Code: Select all

``````1: “A” CLEAR: INPUT N: L=INT(10*N/3): DIM A(255): Z\$=”000000”,T\$=”999999”: WAIT 0
2: FOR I=1 TO L: A(I)=2: NEXT I: M=0, P=0: FOR J=1 TO N: Q=0, K=2*L+1
3: FOR I=L TO 1 STEP -1: K=K-2, X=10*A(I)+Q*I, Q=INT(X/K), A(I)=X-Q*K: NEXT I
4: Y =INT(Q/10), A(1)=Q-10*Y, Q=Y: IF Q=9 THEN LET M=M+1: GOTO 7
5: IF Q=10 THEN PRINT STR\$(P+1);LEFT\$(Z\$,M);: P=0, M=0: GOTO 7
6: PRINT STR\$ P;LEFT\$(T\$,M);: P=Q, M=0
7: NEXT J: PRINT STR\$ P: BEEP 2``````
Here's a screenshot of a quick translation to BBC Basic running in JSBeeb:
As you see, it calculates 50 digits in 79 seconds. I'm going to convert everything to integers, which is apparently OK, and see if it runs faster.

It's a spigot program, as previously seen used as a benchmark in these posts: Valentin's work has also appeared in a previous pi-related post:
Last edited by BigEd on Sun Oct 13, 2019 11:01 am, edited 1 time in total.
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

And indeed, an integer version computes 50 digits in 54 seconds:
flaxcottage
Posts: 4404
Joined: Thu Dec 13, 2012 8:46 pm
Location: Derbyshire
Contact:

### Re: Calculating digits of Pi in Basic

I bet it is quicker on a Pi3 under RISCOS.
- John

Check out the Educational Software Archive at www.flaxcottage.com
cmorley
Posts: 1404
Joined: Sat Jul 30, 2016 8:11 pm
Location: Oxford
Contact:

### Re: Calculating digits of Pi in Basic

Can you post the BBC BASIC version as plain text please Ed?
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

I'd like to, but I'd need to type it in... that's a drawback of experimenting in JSBeeb.
dv8
Posts: 351
Joined: Mon Jun 22, 2009 10:07 pm
Contact:

### Re: Calculating digits of Pi in Basic

This is the listing I typed in.
I changed the / to DIV in lines 100 and 120 which gets the time down to 48 secs.

Code: Select all

``````   10INPUT"How many digits",N%
20T%=TIME
30L%=10*N%/3+1:DIM A%(L%)
40Z\$="000000":T\$="999999"
50FORI=1 TO L%:A%(I)=2:NEXT
60M%=0:P%=0
70FOR J%=1 TO N%:Q%=0:K%=2*L%+1
80FOR I%=L% TO 1 STEP -1
90K%=K%-2:X%=10*A%(I%)+Q%*I%
100Q%=X%DIVK%:A%(I%)=X%-Q%*K%
110NEXT
120Y%=Q%DIV10:A%(1)=Q%-10*Y%:Q%=Y%
130IF Q%=9 THEN M%=M%+1:GOTO170
140IF Q%=10 THEN PRINT STR\$(P%+1);LEFT\$(Z\$,M%);:P%=0:M%=0:GOTO170
150PRINT STR\$ P%;LEFT\$(T\$,M%);
160P%=Q%:M%=0
170NEXT
180PRINT STR\$ P%:PRINT TIME-T%:VDU7
``````
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

Excellent, thanks!
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

Edit: this code appears to be bogus! Do not use!

We can go a little faster if we use peeks instead of array accesses.
50 digits in 50 seconds.

Code: Select all

``````   10INPUT"How many digits",N%
20T%=TIME
30L%=10*N%/3+1:DIM A% L%
40Z\$="000000":T\$="999999"
50FORI=1 TO L%:A%?I=2:NEXT
60M%=0:P%=0
70FOR J%=1 TO N%:Q%=0:K%=2*L%+1
80FOR I%=L% TO 1 STEP -1
90K%=K%-2:X%=10*A%?I%+Q%*I%
100Q%=X%DIVK%:A%?I%=X%-Q%*K%
110NEXT
120Y%=Q%DIV10:A%?1=Q%-10*Y%:Q%=Y%
130IF Q%=9 THEN M%=M%+1:GOTO170
140IF Q%=10 THEN PRINT STR\$(P%+1);LEFT\$(Z\$,M%);:P%=0:M%=0:GOTO170
150PRINT STR\$ P%;LEFT\$(T\$,M%);
160P%=Q%:M%=0
170NEXT
180PRINT STR\$ P%:PRINT TIME-T%:VDU7
``````
Last edited by BigEd on Mon Oct 14, 2019 5:53 pm, edited 1 time in total.
jgharston
Posts: 4257
Joined: Thu Sep 24, 2009 12:22 pm
Location: Whitby/Sheffield
Contact:

### Re: Calculating digits of Pi in Basic

Removing the spaces and replacing PRINT STR\$ P%; with PRINT ;P%; speeds it up another little smidge.

Code: Select all

``````\$ bbcbasic
PDP11 BBC BASIC IV Version 0.32
>_``````
jgharston
Posts: 4257
Joined: Thu Sep 24, 2009 12:22 pm
Location: Whitby/Sheffield
Contact:

### Re: Calculating digits of Pi in Basic

Also, technically, around about 20% of the speed of the program is actually testing the speed of the VDU drivers, not the speed of calculating PI. If you juggle it around a bit to store the digits in memory and then print them afterwards, you'd be testing the calculation speed.

Code: Select all

``````\$ bbcbasic
PDP11 BBC BASIC IV Version 0.32
>_``````
jgharston
Posts: 4257
Joined: Thu Sep 24, 2009 12:22 pm
Location: Whitby/Sheffield
Contact:

### Re: Calculating digits of Pi in Basic

Timing just the calculation, 50 digits in 44 seconds:

Code: Select all

``````   10 REM > PIdigits
20 REM Calculate digits of PI
30 REM Original by Valentin Albillo for HP and Sharp calculators
40 REM Converted by BigEd for BBC BASIC
50 :
60 INPUT"How many digits? "N%
70 T%=TIME
80 L%=10*N%/3+1:DIMA%L%,B%N%:C%=B%
90 Z\$="000000":T\$="999999"
100 FORI%=1TOL%:A%?I%=2:NEXT
110 M%=0:P%=0
120 FORJ%=1TON%:Q%=0:K%=2*L%+1
130   FORI%=L%TO1STEP-1
140     K%=K%-2:X%=10*A%?I%+Q%*I%
150     Q%=X%DIVK%:A%?I%=X%-Q%*K%
160   NEXT
170   Y%=Q%DIV10:A%?1=Q%-10*Y%:Q%=Y%
180   IFQ%=9:M%=M%+1:GOTO220
190   IFQ%=10:\$C%=STR\$(P%+1)+LEFT\$(Z\$,M%):P%=0:GOTO210
200   \$C%=STR\$P%+LEFT\$(T\$,M%):P%=Q%
210   C%=C%+M%+1:M%=0
220 NEXT
230 \$C%=STR\$P%
240 T%=TIME-T%
250 IF N%<254:PRINT \$B% ELSE FOR C%=0 TO N%:VDU B%?C%:NEXT:PRINT
260 PRINT T%;"cs"
``````
Could well be speeded up some more by concatenating lines.

Code: Select all

``````\$ bbcbasic
PDP11 BBC BASIC IV Version 0.32
>_``````
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

There's a thing you can do, to calculate in base 100 or even base 10000, which is more efficient. Here's some BCPL as a hint, by revadlinho:
https://github.com/revaldinho/opc/blob/ ... got-bcpl.b
scruss
Posts: 325
Joined: Sun Jul 01, 2018 4:12 pm
Location: Toronto
Contact:

### Re: Calculating digits of Pi in Basic

jgharston wrote:
Sun Oct 13, 2019 2:23 pm
Timing just the calculation, 50 digits in 44 seconds:
Or in BBC BASIC for SDL 2 on a i7-4790K @ 4.00GHz, 4400 digits in 44 seconds.

Couldn't get it to run at all in Matrix Brandy on the same machine. It failed with Address exception at line 100. I suspect a 64 bit problem, as it seems to run fine on a Raspberry Pi.

A Raspberry Pi 4 manages 5000 digits in 44 seconds.
scarybeasts
Posts: 605
Joined: Tue Feb 06, 2018 7:44 am
Contact:

### Re: Calculating digits of Pi in Basic

BigEd wrote:
Sun Oct 13, 2019 11:48 am
I'd like to, but I'd need to type it in... that's a drawback of experimenting in JSBeeb.
What do you think jsbeeb could offer to make this sort of thing easier?

Cheers
Chris
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

Perhaps *SPOOL to the copy/paste buffer, or into a little text area from which one could copy and paste? If not *SPOOL, then capture the RS432 output... for which we need to know some *FX trickery. But wait: the OS supports a printer, and control-B enables it, so how about capturing that output into a text area?
Richard Russell
Posts: 1909
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

### Re: Calculating digits of Pi in Basic

scruss wrote:
Mon Oct 14, 2019 1:52 am
Couldn't get it to run at all in Matrix Brandy on the same machine.
It runs fine in BBC BASIC for Windows and in BBC BASIC for SDL 2.0 (in the latter case on a 32-bit platform; the modification to use indirection rather than an array has of course broken 64-bit compatibility).
I am suffering from 'cognitive decline' and depression. If you have a comment about the style or tone of this message please report it to the moderators by clicking the exclamation mark icon, rather than complaining on the public forum.
Richard Russell
Posts: 1909
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

### Re: Calculating digits of Pi in Basic

BigEd wrote:
Mon Oct 14, 2019 9:30 am
But wait: the OS supports a printer, and control-B enables it, so how about capturing that output into a text area?
Can't you currently 'print' to a PDF and copy-and-paste the text from that?
I am suffering from 'cognitive decline' and depression. If you have a comment about the style or tone of this message please report it to the moderators by clicking the exclamation mark icon, rather than complaining on the public forum.
Rich Talbot-Watkins
Posts: 1707
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

### Re: Calculating digits of Pi in Basic

Chris recently added "paste from clipboard" into jsbeeb, in case that makes any of this discussion redundant now!
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

Yes, paste from clipboard was a big help. But I made the tactical error of pasting the Sharp Basic original and then fixing it up within JSBeeb, instead of working on a master copy and re-importing it. So the other half of the function, copy-from-printer, would be very handy. Copy-from-screen might also be handy, and especially straightforward in Mode 7.

I'm not at all sure that printing to PDF and hoping for a text layer would be so straightforward. I did in fact print a screen capture to PDF and then OCR it, but I spent so long fixing up the OCR mistakes that dv8's post got there first!
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

BTW, my switch to indirection rather than array mightn't have helped at all, as I wasn't necessarily timing like-for-like. (Edit: it also seems to produce wrong results!) There's a small win from merging lines in the inner loop, and a small win from converting one, other, or both of the small constants 2 and 10 into integer variables, but neither seems like it's worth doing.

The good news about the cost of I/O vs the cost of computation, is that the more digits you ask for, the more computation there is compared to I/O!
Last edited by BigEd on Mon Oct 14, 2019 5:54 pm, edited 1 time in total.
Rich Talbot-Watkins
Posts: 1707
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

### Re: Calculating digits of Pi in Basic

The two GOTOs will be slower than just combining it all into an IF...ELSE IF... ELSE (the former will search from the start of the program looking for the line (I think), while the latter will just search the current line for the token to skip to). I think it's also worth getting rid of any of the "real" string variables and string functions if possible.
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

My feeling - dangerous, should measure it really - is that almost all the work is in the inner loop, and if that's true, there are only minor gains to be made elsewhere. Of course in part this depends on how many digits you want to compute.

Code: Select all

``````  130   FORI%=L%TO1STEP-1
140     K%=K%-2:X%=10*A%?I%+Q%*I%
150     Q%=X%DIVK%:A%?I%=X%-Q%*K%
160   NEXT
``````
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

(That said, we can improve the GOTO by executing it much less often: put in a NEXT first, and then direct the GOTO to the line after the NEXT.)

(Hmm, I see JGH's two GOTOs have different targets, unlike Valentin's original... and I see that's to do with the deferred printing. But this code may have inherited the incorrectness from my 'use indirection instead of an array' offering, which appears to be broken. Sorry about that.)
Last edited by BigEd on Mon Oct 14, 2019 5:55 pm, edited 1 time in total.
Richard Russell
Posts: 1909
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

### Re: Calculating digits of Pi in Basic

BigEd wrote:
Mon Oct 14, 2019 11:21 am
BTW, my switch to indirection rather than array mightn't have helped at all
As I am increasingly wanting my BBC BASIC programs to run on 64-bit platforms I am trying to change my mind-set away from thinking of indirection as a way of saving time and space to being unhelpful from a compatibility standpoint. Of course BB4W and BBCSDL support 'byte' arrays, e.g. DIM A&(L%), anyway so the saving in space can be achieved that way without any 64-bit complications.
I am suffering from 'cognitive decline' and depression. If you have a comment about the style or tone of this message please report it to the moderators by clicking the exclamation mark icon, rather than complaining on the public forum.
geraldholdsworth
Posts: 769
Joined: Tue Nov 04, 2014 9:42 pm
Location: Inverness, Scotland
Contact:

### Re: Calculating digits of Pi in Basic

I've been watching this with much interest, and running the various codes on BeebEm (BBC Master). I'm getting faster run times that quoted.
Anyway, I noticed that the first digit always seems to '0', and the decimal point is missing. So, I've changed the end slightly:

Code: Select all

``````250 FOR C%=1 TO N%:IF C%=2 VDU46
251 VDU B%?C%:NEXT:PRINT
``````
Times I got for 50 digits are 40.56 seconds and 25.8 seconds (with 6502 co-pro).
Gerald Holdsworth
Repton Resource Page
www.reptonresourcepage.co.uk
Richard Russell
Posts: 1909
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

### Re: Calculating digits of Pi in Basic

geraldholdsworth wrote:
Mon Oct 14, 2019 1:39 pm
I noticed that the first digit always seems to '0', and the decimal point is missing.
The subject line does say 'Calculating digits of Pi', not 'Calculating Pi', so omitting the decimal point and adding any number of leading zeroes is entirely consistent with that.
I am suffering from 'cognitive decline' and depression. If you have a comment about the style or tone of this message please report it to the moderators by clicking the exclamation mark icon, rather than complaining on the public forum.
geraldholdsworth
Posts: 769
Joined: Tue Nov 04, 2014 9:42 pm
Location: Inverness, Scotland
Contact:

### Re: Calculating digits of Pi in Basic

Richard Russell wrote:
Mon Oct 14, 2019 2:39 pm
The subject line does say 'Calculating digits of Pi', not 'Calculating Pi', so omitting the decimal point and adding any number of leading zeroes is entirely consistent with that.
Yep, fair point.

I've found an inconsistency...with 100 digits I get:
3.141592653589793238462643383279502884197168482144759468577743117725357681641304293409126284937791482
But, according to a couple of sources on the web it should start:
3.14159265358979323846264338327950288419716
which is fine, but then continues:
9399375105820974944592307816406286208998628034825342117067
which is different to our output...or am I doing something wrong?

(I should point out that I only checked it because I converted it to Delphi and wanted to check what I had done was right.)
Gerald Holdsworth
Repton Resource Page
www.reptonresourcepage.co.uk
geraldholdsworth
Posts: 769
Joined: Tue Nov 04, 2014 9:42 pm
Location: Inverness, Scotland
Contact:

### Re: Calculating digits of Pi in Basic

Ah, found that jgharston's last listing introduced an error, somewhere. If you run BigEd's first listing, it correctly calculates the digits.
Gerald Holdsworth
Repton Resource Page
www.reptonresourcepage.co.uk
BigEd
Posts: 3744
Joined: Sun Jan 24, 2010 10:24 am
Location: West Country
Contact:

### Re: Calculating digits of Pi in Basic

Sorry, my simple-minded changes to use peek and poke instead of arrays seems to be broken code - possibly because of operator precedence.
scarybeasts
Posts: 605
Joined: Tue Feb 06, 2018 7:44 am
Contact:

### Re: Calculating digits of Pi in Basic

BigEd wrote:
Mon Oct 14, 2019 9:30 am
Perhaps *SPOOL to the copy/paste buffer, or into a little text area from which one could copy and paste? If not *SPOOL, then capture the RS432 output... for which we need to know some *FX trickery. But wait: the OS supports a printer, and control-B enables it, so how about capturing that output into a text area?
The printer idea sounds very interesting because it seems pretty friendly to activate. I hadn't heard of Ctrl-B before. How does that work, is future OSWRCH activity also echoed to the printer port or something like that?

Cheers
Chris