29 Jul
2005
29 Jul
'05
12:21 a.m.
Sean 'Captain Napalm' Conner wrote:
It was thus said that the Great Jerome H. Fine once
stated:
Jerome Fine replies:
While the logic will probably be in FORTRAN 77 under RT-11
on an emulated PDP-11, I might actually check that it all works
on a real PDP-11. However, since FORTRAN 77 is rather nasty
using more than 32 bit integers, I will probably code the routines
in MACRO-11 for 64/128 bit add and compare after I first write
the program for 32 bit integers which can calculate up to 2 billion.
As for endian issues, I can define the most significant word to be
at either end, but I tend to think that I will place the most significant
at the high end of the word since this allows FORTRAN 77 to use
octal to output the value correctly with 64 bit floating point values.
After that, if the run times are reasonable, I can extend the code to
allow 64 bits - although I am not sure why since even running the
code to 20 billion takes more than 10 times 2 billion and doesn't
really prove anything. Looking at google, I have noted that PI(N)
has been successfully calculated up to:
N = 40,000,000,000,000,000,000,000
which is already over 70 bits, although it was not done by finding
the prime numbers, but by calculating Li(N) and then the error
between PI(N) and Li(N).
By the way, are there any standard algorithms for
the
4 basic operations (add, subtract, multiply and divide)
for 128 bit numbers which are composed of 8 * 16 bit
words? As per your suggestion, I would probably use:
CHARACTER * 16 ARRAY ( nnn )
What language? In assembly addition and subtraction are pretty trivial if
you have a carry bit you can use (not all RISC based CPUs have a carry bit).
Just make sure you keep track of endian issues (given an array A[n] is A[0]
the Most Significant or Least Significant word?).
[Snip]
A B C D
W X Y Z
---------------------
AZ BZ CZ DZ
AY BY CY DY
AX BX CX DX
AW BW CW DW
(and don't forget the carries!) One trick you might want to try is to take
advantage of the fact that these are binary values so multiplication becomes
shifts and adds but with larger values like these, doing the multibyte
rotates may not be as effective as using the actual MUL instructions.
For the PDP-11, I tend to understand that MUL is only for signed
16 bit numbers, so I don't think MUL can be useful with unsigned
values which are required for a 64 bit multiple as per the above
example.
CAN SOMEONE PLEASE CORRECT ME IF I AM WRONG???
That said, in MACRO-11, it should not be too difficult to do multiple shift
and add operations. However, maybe someone already had some code
handy?
Division is nasty, but again, works like long
division.
[Snip]
I have some C code that does some of this---one is a C implementation of a
techique Woz used in calculating e to 100,000 digits (as described in Byte
magazine of either Dec 1980 or Dec 1981) and another one that does division
in C, if you are interested.
I am interested!!!!!!!
Thank you for your reply!
Sincerely yours,
Jerome Fine
--
If you attempted to send a reply and the original e-mail
address has been discontinued due a high volume of junk
e-mail, then the semi-permanent e-mail address can be
obtained by replacing the four characters preceding the
'at' with the four digits of the current year.