Calculating digits of Pi in Basic

discussion of beeb/electron applications, languages, utils and educational s/w
User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Calculating digits of Pi in Basic

Post by BigEd » Sun Oct 13, 2019 9:41 am

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:
PiSpigotBasicBeebAbillo.png
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 10:01 am, edited 1 time in total.

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Sun Oct 13, 2019 9:53 am

And indeed, an integer version computes 50 digits in 54 seconds:
PiSpigotBasicIntegerBeebAbillo.png

User avatar
flaxcottage
Posts: 3917
Joined: Thu Dec 13, 2012 8:46 pm
Location: Derbyshire
Contact:

Re: Calculating digits of Pi in Basic

Post by flaxcottage » Sun Oct 13, 2019 10:20 am

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

Image

cmorley
Posts: 1167
Joined: Sat Jul 30, 2016 7:11 pm
Location: Oxford
Contact:

Re: Calculating digits of Pi in Basic

Post by cmorley » Sun Oct 13, 2019 10:42 am

Can you post the BBC BASIC version as plain text please Ed?

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Sun Oct 13, 2019 10:48 am

I'd like to, but I'd need to type it in... that's a drawback of experimenting in JSBeeb.

User avatar
dv8
Posts: 284
Joined: Mon Jun 22, 2009 9:07 pm
Contact:

Re: Calculating digits of Pi in Basic

Post by dv8 » Sun Oct 13, 2019 11:04 am

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

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Sun Oct 13, 2019 11:20 am

Excellent, thanks!

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Sun Oct 13, 2019 11:29 am

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 4:53 pm, edited 1 time in total.

User avatar
jgharston
Posts: 3832
Joined: Thu Sep 24, 2009 11:22 am
Location: Whitby/Sheffield
Contact:

Re: Calculating digits of Pi in Basic

Post by jgharston » Sun Oct 13, 2019 12:47 pm

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.25
(C) Copyright J.G.Harston 1989,2005-2015
>_

User avatar
jgharston
Posts: 3832
Joined: Thu Sep 24, 2009 11:22 am
Location: Whitby/Sheffield
Contact:

Re: Calculating digits of Pi in Basic

Post by jgharston » Sun Oct 13, 2019 1:10 pm

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.25
(C) Copyright J.G.Harston 1989,2005-2015
>_

User avatar
jgharston
Posts: 3832
Joined: Thu Sep 24, 2009 11:22 am
Location: Whitby/Sheffield
Contact:

Re: Calculating digits of Pi in Basic

Post by jgharston » Sun Oct 13, 2019 1:23 pm

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.25
(C) Copyright J.G.Harston 1989,2005-2015
>_

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Sun Oct 13, 2019 2:51 pm

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: 168
Joined: Sun Jul 01, 2018 3:12 pm
Location: Toronto
Contact:

Re: Calculating digits of Pi in Basic

Post by scruss » Mon Oct 14, 2019 12:52 am

jgharston wrote:
Sun Oct 13, 2019 1: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.

User avatar
scarybeasts
Posts: 238
Joined: Tue Feb 06, 2018 7:44 am
Contact:

Re: Calculating digits of Pi in Basic

Post by scarybeasts » Mon Oct 14, 2019 4:23 am

BigEd wrote:
Sun Oct 13, 2019 10: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

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Mon Oct 14, 2019 8: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?

User avatar
Richard Russell
Posts: 1139
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

Re: Calculating digits of Pi in Basic

Post by Richard Russell » Mon Oct 14, 2019 9:18 am

scruss wrote:
Mon Oct 14, 2019 12: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).

User avatar
Richard Russell
Posts: 1139
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

Re: Calculating digits of Pi in Basic

Post by Richard Russell » Mon Oct 14, 2019 9:21 am

BigEd wrote:
Mon Oct 14, 2019 8: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?

User avatar
Rich Talbot-Watkins
Posts: 1583
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: Calculating digits of Pi in Basic

Post by Rich Talbot-Watkins » Mon Oct 14, 2019 9:33 am

Chris recently added "paste from clipboard" into jsbeeb, in case that makes any of this discussion redundant now!

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Mon Oct 14, 2019 10:18 am

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!

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Mon Oct 14, 2019 10:21 am

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 4:54 pm, edited 1 time in total.

User avatar
Rich Talbot-Watkins
Posts: 1583
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: Calculating digits of Pi in Basic

Post by Rich Talbot-Watkins » Mon Oct 14, 2019 11:02 am

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.

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Mon Oct 14, 2019 11:09 am

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

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Mon Oct 14, 2019 11:14 am

(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 4:55 pm, edited 1 time in total.

User avatar
Richard Russell
Posts: 1139
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

Re: Calculating digits of Pi in Basic

Post by Richard Russell » Mon Oct 14, 2019 11:45 am

BigEd wrote:
Mon Oct 14, 2019 10: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.

User avatar
geraldholdsworth
Posts: 581
Joined: Tue Nov 04, 2014 9:42 pm
Location: Inverness, Scotland
Contact:

Re: Calculating digits of Pi in Basic

Post by geraldholdsworth » Mon Oct 14, 2019 12:39 pm

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

User avatar
Richard Russell
Posts: 1139
Joined: Sun Feb 27, 2011 10:35 am
Location: Downham Market, Norfolk
Contact:

Re: Calculating digits of Pi in Basic

Post by Richard Russell » Mon Oct 14, 2019 1:39 pm

geraldholdsworth wrote:
Mon Oct 14, 2019 12: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.

User avatar
geraldholdsworth
Posts: 581
Joined: Tue Nov 04, 2014 9:42 pm
Location: Inverness, Scotland
Contact:

Re: Calculating digits of Pi in Basic

Post by geraldholdsworth » Mon Oct 14, 2019 2:37 pm

Richard Russell wrote:
Mon Oct 14, 2019 1: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

User avatar
geraldholdsworth
Posts: 581
Joined: Tue Nov 04, 2014 9:42 pm
Location: Inverness, Scotland
Contact:

Re: Calculating digits of Pi in Basic

Post by geraldholdsworth » Mon Oct 14, 2019 3:20 pm

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

User avatar
BigEd
Posts: 2838
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Calculating digits of Pi in Basic

Post by BigEd » Mon Oct 14, 2019 4:56 pm

Sorry, my simple-minded changes to use peek and poke instead of arrays seems to be broken code - possibly because of operator precedence.

User avatar
scarybeasts
Posts: 238
Joined: Tue Feb 06, 2018 7:44 am
Contact:

Re: Calculating digits of Pi in Basic

Post by scarybeasts » Mon Oct 14, 2019 7:33 pm

BigEd wrote:
Mon Oct 14, 2019 8: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

Post Reply