Johnny Billquist wrote:
Jerome H. Fine
wrote:
More seriously, if I am using all 16 bits as
unsigned integers, then
the high order bit can't be easily eliminated.
True. And if you don't use all 16 bits, then the MUL instruction deals
with the sign itself anyway, so there is no need to take absolute values
and so on either... In short, a good suggestion in theory, but one that
don't work in real life.
But of course you still haven't reflected on the fact that in FORTRAN-77
you can do 32-bit integer multiplication already...
Jerome Fine replies:
OK. I just checked how FORTRAN 77 internally handles:
INTEGER * 4 ITest1, ITest2, ITest3
REAL * 8 RTest1, RTest2, RTest3
ITest1 = 65536
ITest2 = 10
ITest1 = ITest1 * ITest2
The integer instruction Mul allows only 2 signed 16 bit numbers
that then produce a 32 bit number. When 2 signed 32 bit numbers
are multiplied, FORTRAN 77 first converts them to floating point
numbers, multiplies them as 2 real 64 bit numbers and converts the
result back to an integer. The MulD floating point instruction is
used plus the conversions in each direction. What I am confused
about is why FORTRAN 77 first places the 32 bit integers on the
stack before converting to a real 64 bit floating point number. As
far as I can determine, the order of the 2 * 16 bit words on the
stack is the same as in memory, so I do not understand why a
direct access to memory is not used - unless I am incorrect in
my interpretation of the order of the words on the stack - with
the conversion both from integer to real and real to integer.
Johnny (or anyone else), can you please comment on if it is
necessary for FORTRAN 77 to use the stack? If it is not
needed, why does FORTRAN 77 use this approach?
In addition, the following code is just as efficient in the number of
instructions executed, although repeated use takes more overall
code in the file to be executed (as opposed to a subroutine call):
RTest1 = ITest1
RTest2 = ITest2
RTest3 = RTest1 * RTest2
ITest3 = RTest3
Of course
another
method is to keep all the values below 10,000 decimal which
can then allow me to use FORTRAN much more easily. But
I really prefer to use the full 64 bits.
What 64 bits??? Native integers are 16 bits. You also happen to have
32-bit integers in FORTRAN, but there aren't any 64-bit integers. You have
64-bit entities for REAL*8, but they don't hold 64 bits of mantissa, apart
from the rounding errors always expose yourself to when using FP.
I think I explained this in another e-mail. I use:
INTEGER * 2 ITest1 ( 100, 4 )
REAL * 8 RTest1 ( 100 )
EQUIVALENCE ( RTest1, ITest1 )
with RTest1 being the actual variable I use in subroutine calls which
reduces the complexity (within FORTRAN 77) when an indexed
variable is used.
On the other
hand, if I
use the sieve method to find the primes, I don't need either
multiplication or division, just 64 bit adding and 64 bit compares,
probably increments by 2 and 4 and of course conversion of
64 bit values to decimal output. The last can also be done by
repeated subtraction of powers of 10, so again no division.
Why use the sieve? Unless you have lots of memory, and are trying to list
every prime you can find, it's pretty inefficient. And you don't have lots
of memory in a PDP-11. Assuming you represent every odd number with one
bit (no need for the even ones), and assuming that you can stuff an array
of 50Kbytes, that will still only give you primes less than 400.000.
Absolutely no problem representing that in a 32-bit integer.
I'd go for a simple factorization instead, if you want to search for
larger primes. And then you need division and remainder.
The sieve method allows for repeated use of the sieve buffer
which, for optimum use is 5005 bytes in length which is:
5 * 7 * 11 * 13
This allows the first 6 primes (2, 3, 5, 7, 11, 13) to be
handled without having to specifically eliminate them from
the sieve buffer which eventually makes the search much
more efficient. For a 32 bit search (which allows up to
values of just over 2 billion), this requires a table of
primes of about 5000 elements PLUS a table of just where
within the sieve buffer the next elimination takes place
(for primes greater than 13) which also needs about 5000
elements. That adds up to about 45 KBytes plus another
5 KBytes for storing the repeated sieve buffer. Without
overlays, that leaves about 14 KBytes for code and other
data. It might just fit.
If I find that the program is fast enough to be reasonable,
a 64 bit version is possible, but those 2 tables of 5000
elements of 32 bit values would need to be expanded to
79000 elements of 64 bit values just to attempt to find
primes up to 1 trillion. I will address that question
when I find that the 32 bit version is working and fast
enough to even consider a 64 bit version.
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.
