Re: HPGCC 2: sat_decode_real

Joe Horn wrote:

> Claudio wrote:
>
>> Rational numbers require GCD therefore you need
>> to find prime numbers... it's all much slower.
>
> and manjo wrote:
>
>> i almost forgot about the primes (primes are needed
>> for fraction reduction foremost in addition/substraction)
>
> GCD is not done by prime factorization; it's done with Euclid's
> Algorithm, which does not use primes or factorizing or anything like
> that. Just a few MOD's and it's done.

True.

But the "few" mods are expensive operations, since they require
full 64 bit divisions, in case we are talking about 64 bit rationals.
So Claudio is right, when he says that it's all much slower, since you need
term reduction after each operation. Even with that precaution, the danger
of overflows is very high with a fixed bit width (like 64).
In my opinion, rationals make just sense with arbitrary precision
arithmetic.
The HP-GCC 2.0 distribution contains a feasible BCD library and the
implementation of a "Rational" type isn't particularly difficult on top of
that library.
That doesn't necessarily mean that we will do it, though.
Maybe one of the protagonists here might give it a shot...

best
ibl

.

Relevant Pages

  • Re: Magic number in Boolean
    ... rest are primes or composites. ... but I don't know why you'd bother.) ... For rationals, everything except 0 is a unit. ...
    (comp.lang.java.programmer)
  • Re: x^n + y^n = k (mod m)
    ... integer solutions. ... Here are two possible routes to finding such a thing. ... but there is a solution in rationals, ... has solutions for those primes, ...
    (sci.math)
  • Re: Fundamental Theorem of Arithmetic
    ... Primes are primes independent of the number base. ... instance, it is not true in the rationals, because there are no primes in ... I concluded that as is also the case in Serge Lang "It was therefore one ... The statement above explicitly says "every positive integer" so excuse the ...
    (sci.math)
  • Re: Fundamental Theorem of Arithmetic
    ... factorizations. ... Primes are primes independent of the number base. ... instance, it is not true in the rationals, because there are no primes in ... winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... >> factor 9 via gcd. ... > There's a proof that the method does not work for primes squared. ... To prove that, mess with the algorithm. ... No, I'm not estimating anything. ...
    (sci.crypt)