https://cartesianproduct.wordpress.com/feed

It’s now two years since I began my Riscyforth project of writing a Forth for RISC-V single board computers. But it wasn’t until yesterday that I wrote my first serious/useful (if you like this sort of thing) program for it, a version of Conway’s Game of Life.

(This program wasn’t as long as the unit test suite I wrote before, but it is more useful, I’d argue.)

Why did it take so long to do something ‘useful’? Mainly because I didn’t start writing code that allowed screen manipulation (running on top of the nCurses library) making something other than simple textual output possible (thoug there is still no graphics support). All the other time has been spent on writing the code that implements the core system, support for doubles (which in Forth means double length – here 128 bit – integers) and then floating point code.

The first three months were spent getting my head around the basic concepts which I took from this book – which is out of print and hard to get: I certainly wouldn’t pay the prices being sought on Amazon – but also available online: it’s an excellent introduction to the concepts, if very much written for the 8-bit world of the late 1970s, early 1980s.

Then came a lot of coding. I had decided to write it all in RISC-V assembly because I grew up at a time when all Forth’s were implemented that way for speed – it became obviously quickly that a C implementation wouldn’t be much (any?) slower and probably a lot easier to write, but I have (re-)learnt a lot about assembly as a result so from a personal perspective it’s not been a waste of time. (There is some C in Riscyforth now, it was just too complex to write some of it in assembly and keep my sanity and/or produce efficient code, though the vast, vast majority remains as assembly).

Forth is not exactly a growing language these days (when I told my brother I was doing this he just laughed at how mad it all seemed), and the documentation is very much written by and for people who have been around it for a long time, with all the associated assumptions of shared knowledge and practise that is not ever (in my opinion, anyway) fully and concisely stated that one often sees with such hyper-mature projects.

It’s not that stuff is kept secret, but more than once I found myself having made design choices that ran into trouble when other subtlties of the language crept up. Some hetrodox design decisions (like using 64 bit integers throughout rather than the standard 32 bit) fit well with the language though and were never in doubt.

Now it’s done I am very pleased with it and I also like how fast it is – the program is ‘compiled’ but not to a binary and Forth is somewhere between a scripting langauge and a truly compiled programming tool – hence the term ‘threaded interpreted language’ – but it certainly runs faster than the BASIC interpreter/DSL I wrote in Groovy a decade ago.

Writing the program – which didn’t take long once I’d got enough Curses support – did make me think quite a bit about the things we take for granted in other languages: principally about the concept of a variable.

If you had asked me last week to describe the fuction of a variable to starting programmer I probably would have used some analogy like a bucket into which we thow a value – but that’s really not true for C and most other languages.

In C we can have this:

int x;
int y;
x = 3;
y = x * 2;

The thing is that here x isn’t a bucket into which 3 is thrown – it is, essentially, 3.

But this isn’t true in Forth, where the equivalent code is:

variable x
variable y
0 x !
x @ 2 * y !

The declaration and assignment (0 x !) parts are broadly analogous (though Forth is much less strongly typed than even C), but the subsequent access is crucially different. If that final line in Forth had read x 2 * y ! we would be assigning the memory address of x (doubled) to y. That @ (FETCH) operator looks like a small change but psycologically it is huge and the failure to do it properly and consistently was the biggest problem I had writing the code.

It also comes with the realisation that C variables and C++ references are much more closely related creatures than I had though – because both are automatically dereferenced pointers. My experience here has led me to suspect the difference between a pointer and this sort of ‘reference’ is at the root of a lot of people’s troubles with mathematical abstraction – because if even an experienced programmer can stumble over this sort of stuff then why we would we not expect many children (but not all, obviously) to struggle with similar concepts when they are introduced in school mathematics?

(But I’m not qualified to offer a solution to this problem – or even to assert all that strongly that I’m correct, it’s just a passing observation.)

And what now?

I have enjoied the two years working on Riscyforth but I also have to be honest – I appear to be the world’s only user of it (it is cloned a lot on github but I’ve never had a report from a user or a submitted patch).

I suspect there are better projects to put the effort into, though as of yet I don’t know what and so development may go on for a little while yet.

I’ve made some improvements to the program and so here’s an animation of the output.

Forty-one years after I wrote my first version of this (in Z80 machine code for the ZX80/ZX81) here’s the latest, in Forth (Riscyforth for a RISC-V SBC).

This is hot off the editor, so can no doubt be optimised, but I am pretty pleased with it.

\ Conway's Game of Life in Forth (Riscyforth)
\ Copyright (c) Adrian McMenamin, 2022
\ Loosely inspired by the NCURSES How-To version
\ You may distribute this code or a modified version subject
\ to the terms of the GNU GPL, either version 2 or any later
\ version at your discretion
\ See https://github.com/mcmenaminadrian/riscyforth for latest code

loadmodule ./modules/ncurses/ncurses.so

0 constant startx
0 constant starty
120 constant endx
50 constant endy

variable grida
variable gridb
variable countup

variable scale
endx endy * scale !

: memsetup
    scale @ allocate 0<> IF ." ALLOCATE failed" exit then grida !
    scale @ allocate 0<> IF ." ALLOCATE failed" exit then  gridb !
    scale @ 0 do 0 i grida @ + C! 0 i gridb @ + C! loop
;

: memclean
    grida @ free
    gridb @ free
;

variable aheadx
variable behindx
variable aheady
variable behindy
variable currentpos


: updategrid
    \ swap the numbers about
    @ swap @ 
    grida ! gridb !
    endy starty do
        i 1+ endy mod aheady !
        i 1- endy mod dup 0< if endy + then behindy !
        endx startx do
            0 countup !
            i 1+ endx mod aheadx !
            i 1- endx mod dup 0< if endx + then behindx !
            \ all the aheadx
            aheadx @ behindy @ endx * +  gridb @ + C@ 1 = IF countup @ 1+ countup ! then
            aheadx @ j endx * +  gridb @ + C@ 1 = IF countup @ 1+ countup ! then
            aheadx @ aheady @ endx * +  gridb @ + C@ 1 = IF countup @ 1+ countup ! then
            \ equal x
            i behindy @ endx * + gridb @ + C@ 1 = if countup @ 1+ countup ! then
            i aheady @ endx * + gridb @ + C@ 1 = if countup @ 1+ countup ! then
            \ behindx
            behindx @ behindy @ endx * + gridb @ + C@ 1 = IF countup @ 1+ countup ! then
            behindx @ j endx * + gridb @ + C@ 1 = IF countup @ 1+ countup ! then
            behindx @ aheady @ endx * + gridb @ + C@ 1 = IF countup @ 1+ countup ! then
            \ now update display grid
            i j endx * + dup currentpos !
            gridb @ + C@ currentpos @ grida @ + C!
            countup @ 3 > if 0 currentpos @ grida @ + C! then
            countup @ 3 = if 1 currentpos @ grida @ + C! then
            countup @ 2 < if 0 currentpos @ grida @ + C! then
        loop
    loop
;


: displaygrid
    endy starty  do
         endx startx do
            i j endx * + grida @ + C@
            1 = If j i 55 mvaddch else j i 32 mvaddch then
        loop
    loop
    refresh
;

: initgrid
  1 19 15 endx * + grida @ + C!
  1 20 15 endx * + grida @ + C!
  1 21 15 endx * + grida @ + C!
  1 19 16 endx * + grida @ + C!
  1 19 17 endx * + grida @ + C!
  1 21 16 endx * + grida @ + C!
  1 21 17 endx * + grida @ + C!
  1 19 18 endx * + grida @ + C!
  1 39 16 endx * + grida @ + C!
  1 40 16 endx * + grida @ + C!
  1 41 16 endx * + grida @ + C!
  1 39 17 endx * + grida @ + C!
  1 39 18 endx * + grida @ + C!
  1 41 17 endx * + grida @ + C!
  1 41 18 endx * + grida @ + C!
  1 0 0 endx * + grida @ + C!
  scale @ 0 do i grida @ + C@ i gridb @ + C! loop 
;
            
             
: life
    memsetup
    initscr
    clear
    raw
    keypadstd
    noecho
    initgrid
    displaygrid
    begin getch 1 key_f = while grida gridb swap updategrid displaygrid repeat
    memclean
    endwin
;   

The old joke is that Forth is a “write-only language”. in other words, you can write this stuff but you cannot understand it (and hence maintain it).

Of course, any endorsement of this view is regarded as a heresy amongst many in the Forth community, but I have to admit that sometimes the Forth-bashers have a point.

And yet, I have just translated this simple C program from the Ncurses HOW-TO to Forth (specifically my Riscyforth) and it doesn’t look all that complex to me.

(Curses/Ncurses is the best/standard way to build an interface on a terminal or a terminal emulator. With windowing GUIs it might feel like yesterday’s technology but it’s still very widely used and supported – eg for Python.)

Here’s the C (the spelling errors in the comments are as per the original which can be found here):

#include <ncurses.h>

int main()
{	int ch;

	initscr();			/* Start curses mode 		*/
	raw();				/* Line buffering disabled	*/
	keypad(stdscr, TRUE);		/* We get F1, F2 etc..		*/
	noecho();			/* Don't echo() while we do getch */

    	printw("Type any character to see it in bold\n");
	ch = getch();			/* If raw() hadn't been called
					 * we have to press enter before it
					 * gets to the program 		*/
	if(ch == KEY_F(1))		/* Without keypad enabled this will */
		printw("F1 Key pressed");/*  not get to us either	*/
					/* Without noecho() some ugly escape
					 * charachters might have been printed
					 * on screen			*/
	else
	{	printw("The pressed key is ");
		attron(A_BOLD);
		printw("%c", ch);
		attroff(A_BOLD);
	}
	refresh();			/* Print it on to the real screen */
    	getch();			/* Wait for user input */
	endwin();			/* End curses mode		  */

	return 0;
}

And here’s the Forth (sadly Forth sytntax highlighting isn’t supported by the widget and so I haven’t commented the Forth code as it would just be clutter here):

loadmodule ./modules/ncurses/ncurses.so
variable chx 
: main
initscr
clear
raw
keypadstd
noecho
S\" Type any character to see it in bold\n" printw
getch dup chx !
1 KEY_F =
if S" F1 Key pressed" printw
else
S" The key pressed is " printw boldon chx 1 printw boldoff
then
refresh
getch
endwin
;

My Ncurses library is not standard Forth (there isn’t a standard for this) and largely maintains same call names as the C library (many of the Forth functions are just wrappers around the library).

So, if you are a C programmer – can you understand the code? Here’s a few tips to help.

loadmodule is my non-standard extension to load the compiled Ncurses library, that gives me the Forth commands I need.

: and ; delimit my word definition – here I am defining a new word called main that implements what the C main does.

S\" gives me a “counted string” – an address and a string length that is the standard Forth way of handling strings, I have used S\" and not the more usual S" because this form interprets escaped characters.

My printw expects a counted string (so is a little more complex than simple wrapper around the library printw) and I ‘fake’ one by setting up the inputed character as a string of length 1.

Forth has an IF ELSE THEN construct but as Forth pulls everything off the stack the condition has to be evaluated before the IF.

Today is, for me, the last working day of the year and I was able to finish with a small triumph – successfully solving several programming conundrums that have eaten into my time over a number of weeks.

The technology involved – Python – is not one I have had much experience with, and only this morning I was wondering if I’d just bitten off more than I could chew. So getting (the test system) Jenkins to “go green” with all the required functionality in place, feels like a little big deal where I am sitting.

It also reminds me of one of my favourite school days – fifty years ago this week. That term I had started at a new school – because my old one was successively occupied by the British Army and then by the families the British Army displaced when they moved out of the school. Nineteen seventy-two was the maddest, most awful, year of “the Troubles” and West Belfast was right at the heart of it.

I didn’t mind moving, I wasn’t all that happy at the old school and my new “P3” (the same age as American first graders) teacher Mrs MacManus was wonderful.

That week she had held an “essay” competition and we were all challenged to write a Christmas story. On the final day of term she handed out prizes to the top three (in reverse order). By the time she’d announced who came second all my hopes were gone – I was surely not going to be better than those boys. But – as I’m sure you’ve by now guessed – I won, and got a stocking full of sweeties to take home along side the sense of achievement. The flood of happiness as I walked out of class (a half day) immediately afterwards was enormous.

If I had an ambition for the future at that time, though, it wasn’t to be an essayist or any sort of professional writer, but to be some sort of “scientist”. Never made it, of course (I don’t really think that computer “science” is a science at all, as opposed to a form of applied mathematics), and, in fact, I spent much more of my working life being dependent on writing ability – for good or ill – than anything else.

Until, that is, three years ago, when having finally completed my computer science PhD, I decided I had, actually, to get a job writing computer programs.

I was exceptionally lucky: what became my employers described my job interview in the otherwise deserted office as the last face-to-face meeting they were likely to have with anyone for some time. The official lockdown had not yet begun but already the drawbridges were being raised.

Occasionally since then friends express a mixture of wonder and puzzlement at the change of tack – often because it feels to them, I think, that I’ve entered some realm of immense complexity that is simply beyond their understanding. My retort that programming a computer – at a basic level – isn’t really a higher skill seems to cut little ice.

I don’t mean that anyone could write good programs, but I do think that most people could write a program after not much study. While algorithm is much over-used word, an algorithm is actually a set of simple steps towards an end, and it was no accident that Turing’s seminal model of computing was based on the very simple idea of reading and writing a character at a time on a strip of paper.

This is why I do think that, in the next decade and maybe even sooner, we will see AI systems make big inroads into writing computer programs. In environments where computing power and space is relatively plentiful and timing is not a factor in whether a computation succeeds or fails, there is simply no reason to expect otherwise.

This simple “coding” is not a art of dark magic, in fact much of it is repetitive “boilerplate” to set up initial conditions for a routine calculation along with “CRUD” to manage the record keeping.

If anything it is the need for so much of this routine stuff that means so many people can make a living out of writing code without actually being necessarily all that good at it. And this is where AI – which in many cases is just going to copy and marginally adapt stuff other people have already written – will cut through like a knife through butter.

Is that awful? A disaster? No. At least not necessarily.

The route to human happiness lies in diminishing the realm of necessity and giving each and every one of us more free time and resources to do nicer and better things. And there is nothing particularly nice about writing page after page of ‘getter and setter’ methods for a Java class.

The issue, of course, is the distribution of the benefits that will come from the change. If it all goes into the pockets of Jeff Bezos, Elon Musk or even Bill Gates that would indeed be bad.

(The days when I thought Bill Gates was the emperor of the evil Windows empire trying to crush us plucky Linux rebels are gone: my compliant is not that Gates is a bad person, he’s demonstrably the opposite, but that no-one should be able to decide so much simply by dint of having money alone.)

But if, instead, the time and money liberated are spread more fairly – not least to train more people to be masters of the opportunities computing power gives us, and not just code monkeys – then it represents classic progress.

What is wrong today is not that technology is destroying livelihoods but that too few people are being allowed to benefit from the changes technology brings.

Earlier this week I noticed that some anti-vax propagandists have a new line of attack – they aren’t denying that vaccination protects you against severe illness from Covid, but they are saying that it is false to claim that vaccination limits the spread of the disease and hence its also wrong to insist that people should be vaccinated to protect others.

I think its important to state that thete is no credible evidence to support this claim. Indeed I want present here a summary of a paper (a preprint, so not peer-reviewed I fully accept) the findings of which, if confirmed, show very clearly that vaccination has a significant impact in stopping the spread of the disease.

It’s not really in dispute that vaccination was highly effective at stopping the spread of earlier variuants, but there has been a question mark over whether that still applied to the Omicron variant. Omicron appears to be, at least in part, a genetic adaption by the virus to evade vaccination effects so it might also have evaded any rediuction in transmission.

The paper suggests:

• A 21% reduction in transmission if an infected person has already had Covid before getting it a second time.
• A 24% reduction in transmission if an infected person hasn’t had Covid before but has had one vaccination shot.
• A further 12% reducation in transmission for each additional shot (up to three shots) – ie a 48% reduction in transmission if an infected person has three shots.

This is all good and important news and actually ought to make governments (such as the UK’s) widen the offer of booster shots and not restrict them to a limited group.

The UK is currently seeing a sugnificant reduction in its workforce because of illness, widening the offer of booster shots could go some way to fixing that problem.

There is a new release (0.7) of Riscyforth – my Forth for RISC-V based single board computers available – Riscyforth 0.7.

This release adds significant support for 64-bit IEEE754 floating point numbers to broadly match the 2012 Forth standard.

The implementation of the Forth floating point word set isn’t yet quite complete and Riscyforth does not operate a separate floating point stack, but I would expect most standard-compliant code to run. If it does not please file a bug report on Github.

Eugene Wigner’s wrote a famous short essay “The Unreasonable Effectiveness of Mathematics in the Natural Sciences” in 1960. To be honest I find it slightly underwhelming: to me mathematics is the abstraction from physical reality and not – as might be implied by Wigner – that our physical universe is a concretised subset of a higher mathematical world.

Yes, it’s true that mathematics includes much that does not have a 1:1 correspondence with the physical world, but so what? Those things that fall out of the abstraction but are not physically real may indeed be beautiful as Wigner says and therefore worthy of study but I fail to see why that makes mathematics in some way a superior or even a governing science.

And we also know that our mathematics is flawed. There are things we know to be true but which cannot be stated in a consistent mathematical system.

Anyway, I am running away from what I really want to say here – which is actually based on the power of simple arithmetic to solve what seem to be complex computational problems and the frustration one feels when that general expectation breaks down.

I am continuing to work my way through an implementation of floating point numbers in Riscyforth, my (largely – see below) assembly-based implementation of the Forth programming language for RISC-V based “single board computers”.

One of the words I need to implement is “F.” – which as the standard says:

Display, with a trailing space, the top number on the floating-point stack using fixed-point notation:

[-] <digits>.<digits0>

This turns out (like quite a lot of floating point stuff) to be quite complex, as to illustrate:

2.567e34 () is stored in just 64 bits: 0x4713C683CDD0F1E4 but should give you an output requiring 288 bits: 25670000000000000000000000000000000.0

It’s a basic law (via thermodynamics) that in general one can’t get more information out of a system than is input and so this results in approximations and inaccuracies in floating point.

And sure enough my system renders this number as 25670000000000001040660444662064020.0 while a reference implementation gives me 25670000000000001087462021865144320.0. In this case my representation is actually more accurate than the reference by about a factor of but both are out by around – which doesn’t sound like a lot and generally isn’t – it’s about a millimetre on an Earth – Jupiter scale, for instance, but even these small differences start to matter as you multiply them up – which is why planetary probes avoid floating point and prefer arbitrary length integer calculations (or so I am told).

Now 2.567e34 is actually an integer and the maths to generate the number to be displayed are not too complex: the floating point representation is an encoding of , or if you prefer in binary:

100111100011010000011110011011101000011110001111001000000000000000000000000000000000000000000000000000000000000000

And it’s not that hard to convert that to base 10 characters using integers – you repeatedly divide by 10 (1010 in binary) and take the remainder as the character. This is simple to show in base 10 – even if it sounds slightly tautological:

576 / 10 = 57 remainder 6

57 / 10 = 5 remainder 7

5 / 10 = 0 remainder 5

Reverse the output order of 675 and you have 576

That is all great – and so surely producing the digits for the fractional part will be similarly straight forward and an algorithmic process requiring only integer arithmetic available?

No, appears to be the answer, and I find this is deeply perplexing from a philosophical view – hence the idea that arithmetic is “unreasonably ineffective” in this case.

Volume two of Donald Knuth’s masterwork – The Art of Computer Programming – lists (pp 319 – 320 in my 2nd edition) two methods of calculating the fractional part…

(Knuth’s Method 2a):

For radix- (for us is 10) fraction of a binary fraction ie we have:

(where translates to )

Or (Knuth’s method 2b):

Going from we get as the sum:

The problem with both of these methods is that they involve fractional numbers. Now we could possibly/probably eliminate the fractions by, e.g., using 2b with lots and lots of bit shifting (300 or more in some cases) and storing results across a scratchpad of multiple bytes but it would be horrendously complex (even given that I have opted to implement this all in C as assembly is just too complex/inexpressive).

So I have opted for method 2a and using floating point to decode floating point:

int64_t fpStringProcessFraction(char* buffer, uint64_t mantissa, int64_t power, uint64_t sign, uint64_t radix, uint64_t endIndex)
{
        /* find smallest digit */
        uint64_t bit = 1;
        uint64_t displacement = 0;
        while ((mantissa & (bit << displacement)) == 0) {
                displacement++;
        }
        if (power >= 0) {
                power = 1;
        } else {
                power = -1 * power;
        }
        double fraction = 0.0;
        for (uint i = 63; i >= displacement; i--) {
                if ((mantissa & (bit << i)) != 0) {
                        fraction += 1.0 / pow(2.0, power);
                }
                power++;
        }
        bool startedOutput = false;
        uint64_t digitsLeft = 15; 
        uint64_t totalOutput = 0;
        uint64_t powerUp = 1;
        while (digitsLeft) {
                double bigResult = fraction * pow(radix, powerUp++);
                char digit = fpStringGetDigit(bigResult, radix);
                if (!startedOutput && digit != 0) {
                        startedOutput = true;
                }
                if (digit > 9) {
                        digit += 55; 
                } else {
                        digit += 48; 
                }
                buffer[endIndex--] = digit;
                if (startedOutput) {
                        digitsLeft--;
                }
        }
        /* Now reverse the digits */
        uint64_t rightSide = 1023;
        uint64_t leftSide = endIndex + 1;
        while (leftSide < rightSide) {
                char rChar = buffer[rightSide];
                char lChar = buffer[leftSide];
                buffer[leftSide++] = rChar;
                buffer[rightSide--] = lChar;
        }
        /* check for shift left */
        int shiftLeft = 0;
        uint64_t shiftLeftIndex = 1023;
        while (buffer[shiftLeftIndex--] == '0') {
                shiftLeft++;
        }
        if (shiftLeft != 0) {
                shiftLeftIndex = 1023;
                uint64_t mvCharIndex = shiftLeftIndex - shiftLeft;
                while (mvCharIndex > endIndex) {
                        buffer[shiftLeftIndex--] = buffer[mvCharIndex--];
                }
                endIndex += shiftLeft;
        }
        return endIndex;
}

What is “floating point”?

How do you represent a number like in a compressed and useful way in binary?

Any computer science student will be able to tell you that you use a “floating point” representation and, like me a couple of months ago, could probably move on to a hand-wavy explanation that you stored a representation of the exponent (here from ) and what I am choosing to call the mantissa (a practice denounced in the multi-volume bibles of computing algorithms by Donald Knuth) – here – all in one “number”.

And, to be honest, until recently that, and the knowledge that integer (i.e. counting number-based) arithmetic was much, much faster, was all I needed to know.

What is “Riscyforth”?

But that changed when I decided I had to add support for floating point numbers to Riscyforth – my assembly-based Forth for single board RISC-V based computers (SBCs).

I have long-since grown out of the fantasy that Riscyforth will have a mass audience. Indeed there have been moments over that last two years where the idea that widespread adoption of RISC-V – so often touted as the route to an open hardware future to match that of open-source software – has also looked fantastical (though plans for more RISC-V SBCs are now starting to emerge again).

So that means Riscyforth primarily, for now at least, exists for my use, learning and pleasure. I’m not against others using it, indeed I’d love that to happen: being told well over a decade ago that some Perl I’d written was being packaged for a BSD distribution is still a highlight. But in the absence of that I am continuing to pursue the “because it’s there” approach.

Floating point in Forth

Forth’s basic tool is the stack – more or less everything comes and goes via a First In Last Out (FILO) list – so in (integer) Forth the command (known as a ‘word’ in Forth) * multiplies the top two numbers on the stack (consuming them as it does so) and leaves the result on the stack.

That means avoiding, where reasonable and practical, just using existing C library routines and instead trying to write stuff myself, and so it is with parsing floating point numbers off the Forth input stream.

For a Forth floating point calculation we might have this:

3.141 2.56E2 F*

Which means put 3.141 on the stack, then put on the stack and then multiply them (treating them both as floating point numbers) and put the result on the stack.

So my task here is get the character strings “3.141” and “2.56E2” into floating point form and on to the stack. Implementing “F*” is much simpler: just take the numbers off the stack, place them in floating point registers (my RISC-V processor has 32 of these, each 64 bits long) and call the “fmul.d” built-in instruction to multiply the two (double-length or 64 bit) registers together using the floating point circuitry embedded in the central processing unit. That instruction places the result in a floating point register and I then have to place that back on the stack. That can all be done in just six assembly instructions, just as with the integer equivalent: though the calculation is still much, much slower even with the dedicated electronics.

The floating point standard

Floating point numbers are generally represented in today’s computers according to the IEEE754 specification, and as I have already noted I am using the “double” format as standard. Forth’s own standards generally grow out of the 1970s when 16-bit and then 32-bit computing was the norm for even “mainframe” computers, but there seems little sense to me to restrict myself to that when 64-bits, as it were “come for free”.

So I have 64 bits to play with, giving me one bit for the sign, 11 bits for the exponent and 52 bits (the Wikipedia article confusingly says 53, though clarifies why) for the mantissa.

The biggest complication is the exponent/index, because while humans generally count in base 10, your computer and its circuits use base 2 and that includes the exponents. So we don’t want the of but the of and – to make it harder still, when you calculate what should be, you have to change the mantissa too.

How does it work? Let’s look at :

Of course which is represented in binary as and so, multiplying those powers of 2 out, you have this equality:

But while that gives us insight into how to solve this, it’s not the solution because we cannot store multiple exponents in our single representation. Furthermore, if we instead stored the multiplied out exponent we could get no higher (and assuming we used half the available bits to store negative exponents, though dropping that doesn’t actually help) than : for although we could represent -256 to 256, only -100, -10, -1, 1, 10 and 100 would correspond to powers of 10.

Instead we take the highest power here – 6 from , use that as the exponent and add the other factors to the mantissa – recalling that all this is conducted in base 2 (binary):

Because, of course, is half of or, simply, .

Hence we need to calculate the exponent and update the mantissa. The procedure for negative indices is based on similar principles but the details are – as they say – left as an exercise for the reader.

And, as alluded to above, we quickly start to use approximations: as we can only use 11 bits. Similarly, only having 52 bits available for the mantissa requires approximation there too. In fact approximations are overwhelmingly the general case with floating point numbers.

The algorithm in broad form

Here is quick guide to the steps my code takes – I’m not saying this is the best approach, just one that seems to work:

1. Firstly, test if this is a valid representation of a floating point number – does it have a decimal point or an “E” for an exponent and does it only have digits, signs and a single . and/or single E. If it’s not valid reject it as a floating point and have the input parser test it for something else.
2. Note the sign of the mantissa but conduct all the calculations using positive numbers only.
3. Sum the mantissa as though it was an integer – hence 2.54 becomes 254, but noting that we need to adjust the exponent by (in this case) -2.
4. Adjust the supplied exponent as indicated in step 3 and then compute the index of highest bit in the adjusted number – that is our power of 2 exponent, whilst the other bits (shortened if necessary) allow us to calculate the additions.
5. Compute the adjusted mantissa by adding right shifted products where the bits of the exponent are on: e.g., if the base 2 exponent is 6 and bit 5 of the exponent index calculated in step 4 is on (i.e. 1), add half of the original mantissa (i.e., the original mantissa bit shifted by one place to the right) to the original and store that as the (transitory) updated mantissa – repeat this process for all the bits in the index calculated in step 4 (always using the original mantissa as the basis of the shifts, which grow as we move down the index).
6. We use 64 bits to calculate the new mantissa, but now we shorten that 52 by dropping the first and then rounding the numbers that are left – noting that a rounding may require a further adjustment (eg if we round we get and so we have to increment the exponent and store the mantissa as just .
7. Adjust the sign bit as necessary depending on the result of 2
8. We store the exponent as a positive number only, so we apply a bias. If the exponent is out of range we can return the special negative and positive infinities or just 0.

A semi-worked example

254 =

We have adjusted the index back by two, so it’s now and 10 = . Hence exponent is 3.

So we have

Mantissa becomes:

Our result has now grown to the right by 1 digit in length (i.e., by a factor of ), we we add 1 back to the exponent and we are storing a representation of :

A lot of the everyday calculations we rely on depend on “floating point arithmetic” – in other words an approximation of accurrate mathematics and not actual accurate mathematics.

For the last six weeks or so I have been working on bring floating point arithmetic to “Riscyforth” – my assembly-based implementation of Forth for Risc-V “single board computers”.

I could have just used the software written by other people and piped my calls through to that – but this is as much about a learning process and challenge for as it is every going to be about production code. And it turns out floating point is far from simple.

Typically floating point numbers are represented as though in scientific notation, but using powers of 2, rather than powers of 10. So to from the easy-to-write base 10 number to a binary representation there is a fair amount of long (binary) division required – and in this case – because can only be represented by an infinite series of factions to the power of two, an approximation is required:

The error in that partial sum – which requires 13 bits to store – is “just” 0.035% (it comes to 0.09996420851031553398058252427184 according to Microsoft’s calculator – though, that too is an floating point approximation). But that would be enough to miss a target at the distance of the Moon by 138km.

Typically more accurate FP approximations than this are being used to guide modern engineering – but they are still approximations.