ARM NEON in ObJAsm

Three years ago there was a very extended topic in the Raspberry Pi forums about the suitability of various un-enhanced ¹ languages to numeric tasks. This centred around finding the first fibonacci number with 1 million decimal digits. DavidS was there on the sidelines with his usual promotion of Assembler and BASIC, but the other contributors were fully engaged and there were some really interesting aspects discussed, so that I learned a great deal.

To be part of it, I set about finding a solution in ARM BASIC, using array operations with some modifications of my own invention. I was able to get my solution to finish on my mini.m in about a day and a half! Towards the end, the experts, using various compiled languages, were shaving fractions off substantially less than a second on some quite fast machines.

I then found the Numbers module that Gavin was maintaining. Using that, still in BASIC, I was able to get a result in only a few minutes. While working out how to use Numbers I wrote a StrongHelp manual for it, so if anyone is interested I could post a link.

There are a couple of other things I learnt. First is that the algorithms used in Numbers have dated and there are significantly faster ones around now. The second is that there are C libraries that incorporate all the speed tricks for the fibonacci task and can produce a result in a single line. ;-)

What is needed is a job like the RexEx module, which takes a C library and incorporates it into a RISC OS module. That is probably Zahl, of course, but I have not looked at it yet.

¹ Un-enhanced was taken to mean no libraries or extensions.

Edit: it was fibonacci number not factorial – oops.

I wrote an article The Triumph of Lazy Tables in PiAddict Vol 1. No 6.August 2013, comparing the performance of different algorithms for calculating the fibonacci series. Alas, that magazine is defunct, I believe.

The contradiction between time and space (i.e. storage) is an interesting theme in computer science. Lua makes this explicit. Functions (f(x)) use fixed space but unknown time, tables (f[x]) use fixed time but unknown space. Memoization lets use of tables speed up functions. The dual, using Lua’s metatables, lets use of functions enlarge tables.

That set me thinking back to school days.
(Slightly divergent: Pascal’s triangle)
A triangle of values where the two values above add to produce the value and with the n+1^th line giving the coefficients of the expansion of (x+y)ⁿ

Our schoolboy minds quickly realised we could use a tetrahedron of values in the same way for (x+y+z)ⁿ
So for me the next step was (w+x+y+z)ⁿ with a conundrum about how to represent the coefficient values. The tetrahedron already ran foul of the limitations of a flat sheet of paper.

I had a long email correspondence with Richard Hallas, when he was editor of Foundation Risc User, about how people differ in their imaginations, particularly how they see numbers.

Our schoolboy minds quickly realised we could use a tetrahedron of values in the same way for (x+y+z)n

Good for your schoolboy minds. I think you were unusually quick.

the performance of different algorithms for calculating the fibonacci series

Both the discussion and my reading around it introduced me to several of those. My own attempts used only slightly enhanced Karatsuba method.

Memoization lets use of tables speed up functions.

Now there’s a concept that was new to me and cropped up a lot in the fibonacci topic. Nothing like that for BASIC, although I have learned that the use of precalculated data structures can save a lot of code and time.

That is probably Zahl, of course, but I have not looked at it yet.

I now realise that I did look at Zahl back then, but it is not the module I hoped for and not possible to integrate with BASIC, is it?

Good for your schoolboy minds.

That reminds me of, first Mathematician’s Delight, but especially of the later Prelude to Mathematics, that introduced me to the idea of looking for such patterns.

Both excellent books. Alas, the IMath library, which Zahl uses, is in C and would be hard to integrate with BASIC. I felt a bit guilty that this aspect of Craig-Wood’s BigNumber module I was unable to keep alive. I think he went on to look at some other arithmetics that are possibly interesting for RISC OS. One was to choose the biggest prime, call it p (surprise?), smaller than 2^64. Its residues can be represented within 8 bytes. Modular arithmetic modulo p could be useful, and there are some clever ARM assembler tricks to make it fast. Another useful thing to consider is the Chinese Remainder Theorem. That tells you that modular arithmetic modulo a product of distinct primes can be done by working modulo each prime separately. Ideally you delegate a separate core for each prime. Something for the future, maybe?