Topic: Meggitt Algorithms

Interesting web site. I worked for Monroe Calculator in the mid-1970's writing firmware and algorithms for digital calculators. It was just at the time when calculators where starting to use microcontrollers. We worked on our first micro driven scientific calculator (instead of previous discrete TTL logic designs) that used a Rockwell PPS-4/1 4-bit processor. The processor was so new that we had to write our own tools: assembler, linker. At that time we were using the Meggitt algorithms to calculate all scientific functions. The microprocessor could only ADD, it didn't even have a subtraction opocode - you had to do two's complement arithmetic to subtract. The Meggitt algorithms worked superbly. We choose the Meggitt algorithms over the CORDIC equations mainly because, in general, the Meggitt algorithms are converging; meaning that every subsequent digit of precision that was generated was exact. I think this is one of the most beautiful and important characteristic of the Meggitt algorithms, as the results don't oscillate like Newton-Raphson or Cordic. I still have the firmware listing for the calculator (assembly code of course).

Re: Meggitt Algorithms

Thank you for your interesting feed back.

The J. E.Meggitt's paper is a must to read if you want to understand the algorithms in hand held scientific calculators.
IBM JOURNAL    APRIL 1962 (paper Received by the Journal August 29,1961)

Another source is
J. H.Wensley, “A Class of Non-Analytical Iterative Processes,” TheComputerJournal,    Jan.1959.

If have shown recently the mathematical equivalence of the Meggitt's approach (decimal digit-by-digit) and the Volder's algorithm for the B-58 's Cordic.

http://www.jacques-laporte.org/digit_by_digit.htm

The filiation with the Briggs' Radix Method is quite evident.

The code in the HP-35 (and Classic) ROM is based on Meggitt : (2 phase process) the angle reduction is made by repetitive subtractions and the angle rotations are applied next.

The introduction of the paper tells the whole story :


"It is customary in computers to build an arithmetic unit which is capable of adding, subtracting, multiplying and possibly dividing. To perform more complicated operations it is usual to write routines that use these basic operations, operating on words at a time.
However, in certain cases, digit-by-digit methods exist for the evaluation of certain functions."

According to Steve Leibson

"Cochran started out by analyzing algorithms in general and Volder's CORDIC algorithms specifically. Macmillan explained Volder's algorithms mostly by referring Cochran to Volder's papers so Cochran flew down to Costa Mesa, California one day to talk directly to Volder.
.../...
?Volder explained his own algorithms and also pointed Cochran to other important algorithms including some pseudo multiplication and pseudo division algorithms published by J. E. Meggitt in the IBM Journal in 1962."

Re: Meggitt Algorithms

Hi Can you explain golden rule used in it?? And also how does the x be found on it? Actually I have read few tutorial on it. But it is going out of my head. I appreciate if you share your knowledge with me to improve my grade card. smile

Re: Meggitt Algorithms

aliahlewis wrote:

Hi Can you explain golden rule used in it?? And also how does the x be found on it? Actually I have read few tutorial on it. But it is going out of my head. I appreciate if you share your knowledge with me to improve my grade card.

Ok, But just for your 'grade card', I will repeat what I have already explained, in a few pages of my site.

Briggs discovered his 'golden rule' to build a primary table of logs (the Chiliades) from which he could derive every log using (among other methods) the radix method.

HP and TI calculators used a similar silicon table in ROM and used the radix method.

Now the 'golden rule':
Briggs used common logarithm the logarithm with base 10, but it's easier to explain using natural logarithms (base e).

Say we search ln(5).
He took successive square roots of 5 up to 55 times and then he reached what he called the proportionality zone.
Let us do it only 15 times (on my HP67) :
The result is 1.000049117
and the ln(1.000049117) is approximately 0.000049117 (golden rule)

Reversing the procedure ln(5) is approximately  = 0.0000491176 * 2^15 = 1.609465856 (the error is 2.79 10^-5).

Hope that helps.