Lots of macro assembly and self-modifying code in this project, also lots of optimisations, large and small. It's been a blast.

For some months now I've been thinking about, then eventually collaborating on, a pi program. Dave/hoglet is my team-mate on this, and has (as ever) done most of the actual coding. It's been working, and delivering great results, for a while now, although we can't yet say it's finished.

FAQ:
Do we need another pi program? Yes, of course.
Is this one interesting or different? Yes, indeed.
Is there a silent video with minimal information? Yes, look here.
Is this open source? Of course, repo here.
What does it look like? Like this:


Some full writeups are being posted in this thread over on Stardot:
A tale of two spigots - more digits of pi, and faster
You'll find tabulations, code snippets, a chronology, links, images and even videos over there.

A few highlights, then, in case you haven't already clicked on that link:
- it's a pi spigot, which means it starts producing digits at once - you don't have to wait for the calculation to finish before seeing anything
- written in 6502 assembly, using BeebAsm, with lots of macros for loop unrolling and elaborating variations of code
- Edit to add: we also used Owlet, for early Basic experiments, Beebjit, for accelerated accurate emulation, b2 similarly, and hoglet's 6502Decoder for debugging and profiling. For later and longer runs, we used PiTubeDirect as a very fast 6502 second processor
- almost all the time is in long division, of a bignum by a modest multi-byte divisor, and accumulation of the quotient into a sum
- we have three or four division routines, for different lengths of divisor, and each is patched in place (self-modifying code) for the specific divisor
- the accumulation of terms by addition or alternatively by subtraction is handled by patching in place
- we're using a spigotised version of the 4-term BBP formula (for slightly greater capacity) or the 7-term Bellard formula (for much better speed.)
- the code is written for the BBC Micro, with or without 6502 second processor, is around 8k in size, but need do nothing more OS-specific than print a character (and read the system time.)
- all available RAM can be used for the pi calculation - we can get a little better than 2 digits of pi for each free byte of RAM
- we have a visualisation mode which places the pi calculation workspace in screen memory so you can see what's going on. (Example video here)
- on a BBC Micro we can readily fit a 50000 digit calculation, with a second processor we can push it to 135000. That's using nearly 55k of RAM for the bignums
- on a 2MHz 6502 we can compute 100 digits in under a second, 1000 digits in under a minute and a half, 3000 digits in under a quarter of an hour (like almost all pi calculations, it's quadratic in the number of digits)

Previous threads relating to pi calculations:
the fast realization of π-spigot algorithm
Calculating Pi: HP-41C versus Apple ][
A program for today
Apple Pi: BASIC vs. assembly
computing pi with square roots / RPN calculator build

It's worth noting that a spigot algorithm, which generates successive digits in a very user-friendly way, is not the fastest way to compute pi, on a 6502 or elsewhere. But among spigots, ours seems to be very fast. Also, I believe our program uses less RAM than previous spigots, and less RAM than other means of calculating pi. So our program can compute more digits on any given machine than previous methods - presuming we're only using RAM, and not storage.

Edit: here's a glimpse of some of the code - it's patched in place, so you see immediates which are not in fact constants. This code runs very many times, and versions of this code account for almost all the runtime. This is the listing as output by the assembler, so you don't see the comments or the symbolic names for things:


Edit: here's some corresponding source, from the repo

(As an aside, did I not see that someone has discovered a new way of generating Pi recently? I think one of the mathematical guys on Youtube covered it.)

Neil

I think my aim here was two-fold - first, to share our story a little more widely, as I think it's a really interesting 6502 adventure, and showcases some really nice tools, and second, perhaps to initiate some discussion on two fronts:

- about the use of macros, as a way of making quite a large executable from quite a compact and maintainable source
- about live-patching of code (aka self-modifying code) as a way of seriously improving the performance and also improving the density of the executable

Of course the bignum arithmetic is another good topic for this forum. It so happens that we only needed long division and accumulation, and it was advantageous to fuse those into one, unrolled, replicated, routine.

However, I appreciate that it's quite an arcane topic, and a seriously involved implementation, which took quite some time and ingenuity to put together - so it's not an easy thing to start talking about.

(To answer your aside, I suspect you're thinking of this. As a counter-offering, the video which started this adventure of ours is this one, mentioned by Dave in this thread.)

Very interesting post, Ed. Lot's of good information here - looking forward to digging deeper into this.

Thanks! I'm sure we'll post at least one more update over on stardot, but it feels (presently, to me) like we've nearly reached an end point on this particular project.

Edit: there are many other ways to compute digits of pi, and I wouldn't be at all surprised to be investigating one or more of them in future.

Edit to add, from downthread:

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Well, 355/133 puts the earth's orbit only about ninety miles out of place...

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Ooops, typo.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

For those interested in this kind of bignum adventure on 6502, another related thread and program is Bruce's
500+ digits of e
which references Wozniak's 1981 article and project The Impossible Dream: Computing e to 116,000 Places with a Personal Computer.

(I find it interesting to note that e is a much more amenable number than pi, even though both are transcendental, and I find it marvellous that we've managed to compute even more digits, despite this.)

(I'll pop this note into an earlier post in this thread, in the hope of reaching future explorers interested in this kind of adventure.)

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Scroll, man, scroll! (Though the question is: sideways or upwards?)
:p

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

If a 48K Apple ][ can do it, shouldn't a 64K C-64 be able to do it with some sleight-of-hand (maybe only in ML)?

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)