----- Original Message -----
From: "Cameron Hayne" <email@hidden>
To: "Mike Hall" <email@hidden>; "JavaDev"
<email@hidden>
Sent: Monday, December 20, 2004 9:21 AM
Subject: Re: Math conundrum
> I'm not sure I've really understood what you are asking,
OK, basically I did a little reading on the state of the art for determining
if a number is prime. I thought I would make an attempt at implementing some
of the code java to see how well that did. So I'm looking at c++ code
like...
if (IsPrime(r))
{
const unsigned int m = n % r;
if (m == 0) break;
q = LargestPrimeFactor(r - 1);
if (Powm(m, (r - 1) / q, r) <= 1) continue;
/*
// AKS
if (q >= 4 * sqrt(r) * n.Log()/log(2))
{
s = (unsigned int)(2 * sqrt(r) * n.Log()/log(2));
b = true;
break;
}
*/
// Bernstein
const double cMin = 2 * floor(sqrt(r)) * log(n);
AKS is an implementation of the algorithm that supposedly proved checking
that a number is prime is in polynomial time. "Primes is in P" is what you
might google on if curious. Bernstein's is one of a number of suggested
speedups required because oddly while this proves primes can be
deterministically checked in P it isn't all that fast compared to what is
normally used. Probabilistic methods supposedly are the current quickest
with elliptic methods sounding like the future. I could give the O value for
this but they don't mean all that much to me yet when you start comparing
different coefficients of log like O(log6n) or something like that so I
don't really remember it off hand. Now I would like to try some of this from
java with some fairly sizey integers. BigInteger range anyhow. Now
BigInteger lacks square root so I came up with that. I think I posted that a
bit back. You'll notice I also need log. That seemed more logical from
BigDecimal, Math.log e.g. works with double's and BigDecimal seems more an
extension of that while BigInteger extends int, at least to me. So I started
googling and reading and came up with my question concerning this. The code
I am currently planning on going forward with for log is the following which
I found on a Sun java forum.
/*
* I can be wrong, but from what the documentation shows, a BigDecimal
* would be an unscaledValue/10^scale, being unscaledValue and scale
integers,
* and scale non-negative.
* Mathematics shows us:
* log(unscaledValue/10^scale) =
* log(unscaledValue*10^(-scale)) =
* log(10^(-scale)) + log(unscaledValue) =
* log(unscaledValue) - scale*log(10).
*
* So, I'd implement a log method this way:
*/
public BigInteger log(BigInteger bd) {
return log(new BigDecimal(bd)).toBigInteger();
}
public BigDecimal log(BigDecimal bd) {
double logBD = Math.log(bd.unscaledValue().doubleValue()) -
bd.scale()*Math.log(10);
return new BigDecimal(logBD);
}
A really fairly simple implementation although I wouldn't want to prove the
math involved since I was never real big on log's. I have ported a couple
'c' log implementations to java, one
// Based on Cephes Math Library Release 2.8
and the other based on an IBM multiprecision library.
The pasted code seems much simpler than either and seems on a par for speed.
The interim doubleValue() a little bit of a concern.
Why I'm wondering about BigDecimal and double anyhow, thanks.
Mike Hall mikehall at spacestar dot net
http://www.spacestar.net/users/mikehall
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Java-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/java-dev/email@hidden
This email sent to email@hidden
