Playing with PI on an SC131

[Frank P.]

Well the hardware discussions here over the past few days have been running hot and heavy, so I thought I'd start a new software discussion to sort of balance things out. This is a story about PI (the mathematical constant, not the raspberry kind).

I've built up a hard disk image that you can download here: SC131 PI Hard Disk - hd_pi.img
for experimenting with computing PI on the SC131 using various programming languages and algorithms.

What's on the disk:

    PI.C and PI.COM               A 16-bit program for computing PI up to 22904 decimal places
    PI.SUB                        A submit file for building PI.COM from PI.C using Aztec C (included)

    PI-OL.C and PI-OL.CPM         A somewhat faster 16-bit program for computing PI up to 16275 decimal places
    PI-OL.SUB                     A submit file for building PI-OL.COM from PI-OL.C using Aztec C (included)

    PIZ88.C and PIZ88.COM         PI.C compilable with and cross-compiled by Z88DK on a modern host computer
    PIZ88.BAT                     A Windows/DOS batch file for building PIZ88.COM from PIZ88.C using Z88DK

    PI-OLZ88.C and PI-OLZ88.COM   PI-OL.C compilable with and cross-compiled by Z88DK on a modern host computer
    PI-OLZ88.BAT                  A Windows/DOS batch file for building PI-OLZ88.COM from PI-OLZ88.C using Z88DK

    PI.BAS                        An MBASIC (included) program for computing PI (ported from PI.C by Tom Lake)

    PI32.C                        32-bit version of PI.C that you can compile/run on your favorite modern computer

    TIMEPI.SUB                    Submit file for timing PI.COM (runs TIMER before and after)
    TIMEPIOL.SUB                  Submit file for timing PI-OL.COM (runs TIMER before and after)
    TIMEPIZ8.SUB                  Submit file for timing PIZ88.COM (runs TIMER before and after)
    TIMEPOZ8.SUB                  Submit file for timing PI-OLZ88.COM (runs TIMER before and after)

A little history on this project:

While playing around with a language called FOCAL on my AltairDuino, I ran across a program for computing PI written in FOCAL for the SOL20 by a fellow named Paul Schaper. While the program is fundamentally incomprehensible to me, I learned that it was of a class of algorithms for computing PI known as spigot algorithms. I ported the program to C, compiled it with Aztec C for CP/M, ran it on the AltairDuino, and shared it with the members of the AltairDuino Google group. This led to a discussion which uncovered another spigot algorithm, implemented as one-line of C by Dik Winter based on an algorithm by Rabinowitz & Wagon. I unwound the one-line implementation and de-obfuscated it, then generalized it to allow the number of decimal places to be user specified; this I also compiled with Aztec C for CP/M and ran on the AltairDuino. One thing I quickly realized about both of these programs - they were very slow at Altair 8800 speeds and the compute time for PI increased roughly as the square of the number of decimal places computed.

Since the SC131 is running roughly 9 times faster than an Altair 8800, I first moved these programs over to the SC131 using XM and ran them. Sure enough, they did run about 9 times faster. The original algorithm (PI.C) computed PI to 100 decimal places in 31 seconds, vs. ~270 seconds on the AltairDuino; while the unwound "one-line" algorithm (PI-OL.C) computed PI to 100 decimal places in 19 seconds, vs. ~175 seconds on the AltairDuino.

Then I discovered the cross-compiler Z88DK! When I compiled these two programs for CP/M with Z88DK, I found that the executable programs generated by this more modern compiler technology (vs. Aztec C) ran MUCH faster. PI.C compiled this way (PIZ88.COM) can compute 100 decimal places in just 9 seconds; PI-OL.C compiled this way (PI-OLZ88.COM) can compute the same 100 decimal places in just 6 seconds. I also tried the Z88DK-compiled versions on the AltairDuino with similar speed increases there (though I had to configure the AltairDuino to use a Z80 processor rather than the 8080). I tried to use Z88DK to generate 8080 code but ran into assorted compile errors, so I gave up on that; if anyone knows how to generate pure 8080 code using Z88DK, I'd appreciate advice.

PI.C, when compiled for a 16-bit system, can correctly compute PI to 22904 decimal places. You probably wouldn't want to wait for that many places because it would still take more than 80 hours even using the Z88DK-compiled version PIZ88.COM.

PI-OL.c when compiled for a 16-bit or 32-bit system, can correctly compute PI to 16275 decimal places but will run out of memory for more than 2851 decimal places (with a 55302 byte CP/M TPA). If you happen to boot ZPM3 which has a 60422 byte TPA, it will compute up to 3215 decimal places. Because PI-OLZ88.COM is smaller than PI-OL.COM, it can compute a few hundered more digits without running out of memory. PI-OLZ88.COM computes 2851 decimal places in 2620 seconds;

Also included on the disk image is an MBASIC version of the first algorithm (PI.BAS), ported by Tom Lake of the AltairDuino group. That runs really, REALLY slow, as you might imagine! It can only compute up to about 1984 decimal places and that will take 7 hours or so.

Lastly, on the disk image is the source code for the 32-bit version of the program that can compute PI to at least 1,000,000 decimal places. If you copy that off and compile it with gcc on a modern Intel Core i5 machine, it will gladly compute PI to 100,000 places in maybe 3 minutes, or to 1,000,000 places in less than 5 hours. It's not too shabby on a Raspberry Pi 3 model B either at about 15 minutes for 100,000 places.

You can verify that these programs are computing the correct result by consulting this web site: https://www.angio.net/pi/digits.html

If you download the disk image, you can image it to an SD card by itself (as slice 0), or copy it onto the end of the combo image (as slice 6) or to the end of any single disk image (as slice 1). The disk will boot to ZSDOS (the NZCOM version) so that you can run the things on it, but will contain only the files necessary for this project, not all of the usual CP/M utilities, so you may want to boot from a different disk and just use this as a data disk; if you happen to boot CP/M 3, you should use A:SUBMIT or SUBMIT3 (instead of SUBMIT) on this disk to run any of the .SUB files.

If you have a non-SC131 Z80 CP/M system that does not use RomWBW with SD Card HD slices, but still want to experiment with PI, I've also provided a zip file containing all the individual CP/M files here: pi.zip

[Phillip Stevens]

Frank P. wrote:

I also tried the Z88DK-compiled versions on the AltairDuino with similar speed increases there (though I had to configure the AltairDuino to use a Z80 processor rather than the 8080). I tried to use Z88DK to generate 8080 code but ran into assorted compile errors, so I gave up on that; if anyone knows how to generate pure 8080 code using Z88DK, I'd appreciate advice.

Hi Frank.

8080 code is supported in only one of four major alternatives for z88dk, being the sccz80 compiler, and the classic library. There is a wiki entry on 8080 and how to use it with the +cpm target in classic.

zcc +cpm -clib=8080 pi.c

The sdcc compiler uses index registers, so it is not compatible with 8080, and newlib has no 8080 support either.

I hope that helps.

Phillip

[Frank P.]

Thanks Phillip, I'll give it a shot!

[Frank P.]

Sadly, no cigar. I didn't think it could be something that simple. The compiler in this mode appears to support neither scanf() nor malloc(). For general information, here are the errors from attempting to compile both programs:

zcc +cpm -clib=8080 piz88.c
Warning at file 'piz88.c' line 335: interpreting indirect value as immediate
Warning at file 'piz88.c' line 415: interpreting indirect value as immediate
Error at file 'C:/Users/Frank/Desktop/AltairDuino/z88dk/lib/../lib/crt/classic/crt_runtime_selection.asm' line 96: symbol '__scanf_handle_d' not defined
Error at file 'piz88.c' line 136: symbol 'scanf' not defined
Error at file 'malloc.asm' line 16: symbol '_heap' not defined
Errors in source file C:\Users\Frank\Desktop\AltairDuino\z88dk\lib\config\..\..\\lib\target\cpm\classic\cpm_crt0.asm:
Error at file 'C:/Users/Frank/Desktop/AltairDuino/z88dk/lib/../lib/crt/classic/crt_runtime_selection.asm' line 96: symbol '__scanf_handle_d' not defined
                   ^ ----       defw    __scanf_handle_d
Error at file 'piz88.c' line 136: symbol 'scanf' not defined
                   ^ ---- {
Error at file 'malloc.asm' line 16: symbol '_heap' not defined

AND:

zcc +cpm -clib=8080 pi-olz88.c
Error at file 'C:/Users/Frank/Desktop/AltairDuino/z88dk/lib/../lib/crt/classic/crt_runtime_selection.asm' line 96: symbol '__scanf_handle_d' not defined
Error at file 'pi-olz88.c' line 63: symbol 'scanf' not defined
Error at file 'malloc.asm' line 16: symbol '_heap' not defined
Errors in source file C:\Users\Frank\Desktop\AltairDuino\z88dk\lib\config\..\..\\lib\target\cpm\classic\cpm_crt0.asm:
Error at file 'C:/Users/Frank/Desktop/AltairDuino/z88dk/lib/../lib/crt/classic/crt_runtime_selection.asm' line 96: symbol '__scanf_handle_d' not defined
                   ^ ----       defw    __scanf_handle_d
Error at file 'pi-olz88.c' line 63: symbol 'scanf' not defined
                   ^ ----       if(a==NULL) {printf("Not enough memory\n"); exit(1);}
Error at file 'malloc.asm' line 16: symbol '_heap' not defined

Notice that the references to lines in piz88.c and pi-olz88.c are nonsense references because those lines don't even contain the scanf() function call. However, there is a scanf() call present on a different line. The wiki entry that Phillip referenced does say scanf() is not supported, but it is silent on malloc().

[Phillip Stevens]

Frank P. wrote:

Sadly, no cigar. I didn't think it could be something that simple. The compiler in this mode appears to support neither scanf() nor malloc(). For general information, here are the errors from attempting to compile both programs.

Sorry. I haven't done it before. A bit of digging turned up what I missed.

Automatic malloc() needs to be turned on in the library.

zcc +cpm -clib=8080 -DAMALLOC pi.c

You also need to add an include to the program.

#include <malloc.h>

You could try running your program without scanf(), and if it does what it needs then that functionality could be returned to the library.

Phillip

[Frank P.]

Alas, that makes the errors far worse. I'm giving up on this - it's not that important because I can substitute a (emulated) Z80 processor for the (emulated) 8080 on my AltairDuino by flipping one setting in the configuration. I just thought the members over there would love to be able to cross-compile for the 8080; in 3 years, the subject of Z88DK never came up - I had to come here to learn about it!

[Phillip Stevens]

Frank P. wrote:

Alas, that makes the errors far worse.

Yeah, sorry. As noted, I've not done this before.

 

I just thought the members over there would love to be able to cross-compile for the 8080; in 3 years, the subject of Z88DK never came up - I had to come here to learn about it!

It should be in a working state, and it would be a pity to let it remain floating.

If you have GitHub ID (or are prepared to get one), attach the code to a new issue and it will get fixed (or at least the right incantation will be found).

Cheers, Phillip

[Frank P.]

Thanks for the suggestion Phillip - I just submitted this new issue (with pi.c attached - actually a variation on pi-olz88.c):

Compiling for 8080 - malloc() with -DAMALLOC not working #1528

[Frank P.]

The Z88DK 8080 malloc() library got fixed and I was able to compile a version of pi-ol.c in which I substituted gets() and atoi() for scanf(). But the generated code is no where near as speedy as when Z88DK generates Z80 code - perhaps 1/3 the speed. The sccz80 compiler is apparently older compiler technology and without Z80 opcodes to work with in this mode, doesn't generate such efficient code. Still a bit faster than the Aztec C generated code, but a bit of a disappointment overall. Thanks Phillip for encouraging me to follow through on this. I'll eventually get around to posting this variation and updating the hard disk image.

[Phillip Stevens]

Frank P. wrote:

The Z88DK 8080 malloc() library got fixed and I was able to compile a version of pi-ol.c in which I substituted gets() and atoi() for scanf().

Happy to hear that it is working.

But the generated code is no where near as speedy as when Z88DK generates Z80 code - perhaps 1/3 the speed.

I've found recently that the optimisation options for sccz80 are worth playing with. Moving from -O1 to -O3 more variable management code is pushed to subroutines to reduce program size. This conflicts with going fast, because of the overhead of a call / ret for each memory access and the stack juggling to get around the stacked return address. For working with 16-bit variables, I found that -O1 --opt-code-speed=inlineints produces the fastest results, for example.

The sccz80 compiler is apparently older compiler technology and without Z80 opcodes to work with in this mode, doesn't generate such efficient code.

Still a bit faster than the Aztec C generated code, but a bit of a disappointment overall.

Just to jump to the defense of sccz80 a little. It may have a long history back to smallc, and display some of that heritage today.

But it is as complete as you need, and I'd suggest probably the only 8080 capable compiler under active development.

Why, just last month sccz80 learned about IEEE 16-bit floating point and can now compile half_t floating point without problem.

I doubt there's any other Z80 family compiler that can say that. ;-)

Hope to see further 8080 examples.

Cheers, Phillip

[Alan Cox]

On Monday, 13 July 2020 00:29:27 UTC+1, Phillip Stevens wrote:

Frank P. wrote:

The Z88DK 8080 malloc() library got fixed and I was able to compile a version of pi-ol.c in which I substituted gets() and atoi() for scanf().

Happy to hear that it is working.

But the generated code is no where near as speedy as when Z88DK generates Z80 code - perhaps 1/3 the speed.

That shouldn't be unexpected. The 8080 lacks any useful way to work with stack variables efficiently. Using global/static everywhere can help a bit but the CPU is simply not very good for C (the Z80 is not that much better but has more registers to hide the fact and also the SDCC based compiler has a modern register allocator that uses tons of CPU and gigs of RAM)

The sccz80 compiler is apparently older compiler technology and without Z80 opcodes to work with in this mode, doesn't generate such efficient code.

Still a bit faster than the Aztec C generated code, but a bit of a disappointment overall.

> Just to jump to the defense of sccz80 a little. It may have a long history back to smallc, and display some of that heritage today.

> But it is as complete as you need, and I'd suggest probably the only 8080 capable compiler under active development.

Not the case - The ACK 8080 compiler is also actively developed - although as it's been generating 8080 code for a very long time and the compiler core is also very old it's not showing bugs very often either.  ACK doesn't generate bad 8080 code and but it's not going to be any faster just smaller (ack is tuned for size not speed).

Whitesmiths was probably the best of the old 8080 native C compilers. It knew how to keep BC as a register variable for one.

The 8085 does have a proper instruction set for C and stack based languages, but that doesn't help 8080/Z80 code.

Alan

[Frank P.]

Because the pi-ol.c compilation for 8080 worked but produced slow code, I thought I'd experiment with the other algorithm pi.c. However, another compilation bug cropped up, so I submitted another new issue against Z88DK:

Bug in 8080 compilation for CP/M - extern variable expression evaluation fails #1531

[Frank P.]

So that bug got fixed too (well, technically it's not fixed until tonight's nightly build of Z88DK) and I was able to compile a variation of pi.c for 8080. As expected it is much slower than the Z80 code piz88.com - maybe 2.5 times slower. It all gets pinned on the fact that both programs do a little bit of 32-bit arithmetic (in particular a division) within the inner-most loop of their respective algorithms. The following new issue against Z88DK got generated internally and may (or may not) result in some code improvement in that area as the community ponders the issue:

(8080) Performance of compiled code is worse than expected #1530

I must say that Z88DK member suborb is really on top of the 8080 issues, and things get fixed there fast! Since Z88DK is primarily targeted to the Z80 and its clones, 8080 code generation is not as mature as for the Z80, but it works after a fashion. I'll keep an eye on things there, and if the speed issue looks up, I'll post the Z88DK 8080 code for both PI algorithms here and over in the AltairDuino group. It's never going to be as fast as PIZ88.COM and PI-OLZ88.COM but I'd settle for 75% the speed of those.

[Bill Shen]

I tried you pi.com and piz88.com on my new Z80 SBC, ZRuno, to make sure the new hardware will run your program correctly.  It has a 22MHz clock so pi.com to 100 digits took 27 seconds to compute with this result

HOW MANY DIGETS DO YOU WANT PI TO ?100
THE VALUE OF PI TO 100 DECIMAL PLACES
3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510
  58209 74944 59230 78164 06286 20899 86280 34825 34211 70679

Tried piz88.com and it generated the same result in 6 seconds.

I also compiled pi.c with HiTech C (ver 3.09), the resulting program takes 8 seconds to compute 100 digits, not as good as Z88DK, but quite a bit better than Aztec C.

  Bill

[Frank P.]

With a lot of help from suborb over at the Z88DK development group, I was able to generate pure 8080 code using Z88DK to cross-compile for 8080 CP/M (of course, it will run on Z80 CP/M as well). The 8080 code isn't as blazingly fast as the Z80 code, but suborb was able to do some optimizations for division of long ints so that the Z88DK generated 8080 code runs almost twice as fast as the native Aztec C compiled code, and at about 50% the speed of the Z88DK generated Z80 code.

So I've updated SC131 PI Hard Disk - hd_pi.img and pi.zip to update the Z88DK C source files (to be compilable for both Z80 and 8080) and some new batch files to generate the 8080 versions. I've also added two additional submit files to time the 8080 versions. So...

What's NOW on the disk:

    PI.C and PI.COM               A 16-bit program for computing PI up to 22904 decimal places
    PI.SUB                        A submit file for building PI.COM from PI.C using Aztec C (included)

    PI-OL.C and PI-OL.CPM         A somewhat faster 16-bit program for computing PI up to 16275 decimal places
    PI-OL.SUB                     A submit file for building PI-OL.COM from PI-OL.C using Aztec C (included)

    PIZ88.C and PIZ88.COM         PI.C compilable with and cross-compiled by Z88DK on a modern host computer

    PIZ8080.COM                   PI.C cross-compiled by Z88DK to generate pure 8080 code

    PIZ88.BAT                     A Windows/DOS batch file for building PIZ88.COM from PIZ88.C using Z88DK

    PIZ8080.BAT                   A Windows/DOS batch file for building PIZ8080.COM from PIZ88.C using Z88DK

    PI-OLZ88.C and PI-OLZ88.COM   PI-OL.C compilable with and cross-compiled by Z88DK on a modern host computer

    PIOZ8080.COM                  PI-OL.C cross-compiled by Z88DK to generate pure 8080 code

    PI-OLZ88.BAT                  A Windows/DOS batch file for building PI-OLZ88.COM from PI-OLZ88.C using Z88DK

    PIOZ8080.BAT                  A Windows/DOS batch file for building PIOZ8080.COM from PI-OLZ88.C using Z88DK

    PI.BAS                        An MBASIC (included) program for computing PI (ported from PI.C by Tom Lake)

    PI32.C                        32-bit version of PI.C that you can compile/run on your favorite modern computer

    TIMEPI.SUB                    Submit file for timing PI.COM (runs TIMER before and after)
    TIMEPIOL.SUB                  Submit file for timing PI-OL.COM (runs TIMER before and after)
    TIMEPIZ8.SUB                  Submit file for timing PIZ88.COM (runs TIMER before and after)
    TIMEPOZ8.SUB                  Submit file for timing PI-OLZ88.COM (runs TIMER before and after)

    TIMEPIZ0.SUB                  Submit file for timing PIZ8080.COM (runs TIMER before and after)

    TIMEPOZ0.SUB                  Submit file for timing PIOZ8080.COM (runs TIMER before and after)

So just to give you an idea of the timings, here is approximately the number of seconds on an SC131 that it takes to compute PI to 100 decimal places with each C program:

PI.COM:            33 Seconds         Aztec C

PI-OL.COM:       20 Seconds         Aztec C

PIZ8080.COM:   18 Seconds         Z88DK (pure 8080 code)

PIOZ8080.COM: 13 Seconds         Z88DK (pure 8080 code)

PIZ88.COM:        9 Seconds         Z88DK (runs on a Z80 only)

PI-OLZ88.COM:   6 Seconds         Z88DK (runs on a Z80 only)

NOTE: In order to compile the 8080 binaries from source and get the timings shown above, you need to use the July 17th 2020 nightly build of Z88DK or later. Builds before that will either generate slower code or fail to compile.

[Frank P.]

Somehow, my Google Drive reset the permissions and links to the SC131 PI Hard Disk and the pi.zip files from my the previous post(s). And in their infinite wisdom, Google also took away the ability to edit the previous post(s). So here are the updated links you can use to download the hard disk image and/or the zip file of the individual files (still as described in the post immediately prior to this one):

SC131 PI Hard Disk - hd_pi.img

pi.zip

Sorry about that, I have no idea what's up with Google.

[Bill Shen]

Probably flagged as "misinformation" by Google's AI.  Your previous message contained this phrase "...twice as fast as the native Aztec C compiled code".  We all know Code Talkers are Navajo, not Aztec!  ;-)