The horst algorithm


The Horst algorithm is a combination of base conversion (from base 10 to base 11 to base 12 etc.) and the observation that a number is divisable by 10 if the last digit is zero. There was an explanation of the algorithm in the hcc newsletter 1982, volume 4, april. Some lack of modesty is needed to name a combination of a well known algorithm and a trivial observation after yourself...
Here are some implementations.

The first version ran on a Z80 NASCOM (1979) personal computer with 1 Kbyte of memory. It was able to find factors of unlimited length for numbers of 255 digits, all though it skipped factors under ten. I plan to show a facsimile of the z80 machine code version program (hand written), sorry no assembler available.

The source of the Z80 assembler version for the Osborne 2 (missing)

The source of the ANSI c-version (missing)

The version in Forth horst-cf.frt is very neatly written and has a good explanation. It is in the dutch language and uses the recursive version of the algorithm. It is for 16 bits systems only. It is a tribute to the programming quality of my late friend Adrie Bos. He had his own Forth system, called ComForth. It goes to a maximum of 31 bit dividers on the 16-bit system it was designed for.

The version in Forth horst-a.frt is a post forth-83 version, based on Adries work. This one is in english, and it uses the iterative version of the algorithm. It also uses iforth-compatible locals, as it was converted by Marcel Hendrix. The algorithm is not double precision, but arbitrary-length precision. It has has the property that it will in the end find dividers as large as gigabytes to store them (if you have time to live). It is slightly faster.

After complaints about iso-ness I converted Adries work to horst-iso.frt. This should run without problems on iso systems. This will find 127 bit dividers on a 64 bit system for the patient longliving.

Why my winning entry in the obfuscated C contest is presented in this section? Well, again is a factoring program, in fact an obfuscated version of the Horst algorithm.
I am very proud that this is one of the very few programs in that contest ever, where the c-beautifier nor the c-preprocessor are of any help to analyse the program. Can you spot the bug in the program? And do you understand how the fix helps?

You can comment via email

Other number theoretical stuff
Go to the home page of Albert van der Horst