Anton Ertl wrote:
> Bernd Paysan <bernd.paysan@[EMAIL PROTECTED]
> writes:
>>In Gforth with a 2GHz Athlon64, it takes about
>>1.5ms to run 1000t. I guess iForth64 should do it in less than 1ms, even
>>when the division for the modulus might be the limiting factor.
>
> If you timed it with the development version of gforth-fast, I doubt
> it. I guesstimate that the program spends more then 1ms on UM/MOD on
> your machine.
I had it run with the normal gforth. Gforth-fast on the 2GHz Athlon64:
955µs, on a 2.6GHz Core 2 Quad 650µs. So actually iForth64 must be under
one 1ms, too ;-).
>>&10000000000 Constant mod#
>>
>>: *mod ( a b -- c ) um* mod# um/mod drop ;
>
> Wasn't there a way to do integer division (and consequently compute
> the modulus) by multiplication with the inverse?
Won't help much, since we need to divide a 128 bit number, and that
requires
too many multiplications to get the result (the inverse also must be a 128
bit number to be accurate enough, so we have four multiplications to
divide
down, and then another multiplication to restore the modulus from the
fractional part). It's probably possible to use a 64 bit number and the
right amount of bitshift, but for a Euler problem solution, this is too
much work ;-).
I've tried something else: Using fractional numbers, i.e. scaling by 1e-10
and having the decimal point on bit 64. The problem is the same: If you
use
just a 64 bit inverse of 1e10, you don't have much accuracy left. Using
128
bits requires too many multiplications, and I still didn't get it accurate
enough.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
|
