#
The horst algorithm

###
Introduction

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,
iocc.zip
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