However, word on teh grapevine I have access to says that it seems that Henrik Lenstra (not to be confused with Arjen), has already declared taht he believes the proof to be correct and elegant.
And that's about as high a recommendation as it gets.
I'll try to knock up an implementation of his algorithm some time soon, and see what the practical big-Oh looks like.
x is just a symbol. The proof is performed using polynomial ring.
Doing shit modulo (x^r-1) means that as soon as you multiply your polynomials together and get any terms over x^(r-1) you can replace x^(r+d) with x^d, because (x^(r+d)-x^d) == 0 (mod (x^r-1))
Rabin's test says that if there is no witness below 2ln^2(n), then the number is certainly prime. The repeated-by-a-fixed-small-number PRP-test MR test is still a compositeness test, or a Probable Primality test, and does not give a certain answer.
A PRP is not _proven_ prime.
See professor Caldwell's Prime Pages at: http://primepages.org/
ECPP is already polynomial time with theoretical exponent ~6. However, the best ECPP implementation out there, Marcel Martin's 'Primo', seems to behave as if it has exponent ~4.5-5. ECPP is non-deterministic though. But it looks like this one is too.
So this looks as if it may be worse than the state of the art.
I'll wait for Lenstra and Pomerance to say their piece though, before making my mind up.
No, let me guess you flunked English. Re-read your post. Reread my post. _Understand_ what I've written therein.
Then come back here apologetically when you realise that you've not just made a minor cock-up, which was forgivable, but you've completely missed the point being made by the person who was pointing out your mistake, and thus made yourself look like a total fuckwit. Good darts. Double top, in fact.
And because it's on wiki it must be true, right? Now _that_'s naivete.
"Anonymous Cowards stick their heads up the goatse man's arse", Josef Stalin
How convincing was that? Exactly. Sheesh.
Anyway, about 12 years ago, I remember the purported quote being about "256K", not 640K. 256K being the actual ammount of memory the top of the range systems were being shipped with at the time.
" A decade ago, no one forsaw a need for Ghz processors, GB of RAM, Gigabit ethernet, etc. "
So for example in october 1988, when Arjen Lenstra and Manasse factored the first 'hard' 100-digit number using the Multiple Polynimial Quadratic Sieve, by spreadding the work over ~400 computers around the world, they weren't thinking "I wish computers were ~400 times more powerful"?
I perform hard computations for a hobby - my electricity bill for my home network is $400/year. No future processor is too powerful for me to be able to make use of it.
So, who's censoring whom? Let's look in today's news...
http://www.wired.com/news/politics/0,1283,53873, 00.html {{{ Israel Blocks Palestinian ISP By Noah Shachtman
For hundreds of thousands of Palestinians, getting to work, school or the market has been virtually impossible since Israel's latest anti-terror campaign began. Now, they won't be able to get online, either.
Early Monday morning, Israeli Defense Forces (IDF) troops took over the offices of Palnet, the leading Palestinian Internet service provider, shutting down the firm's operations. The move -- part of Israel's 3-week-old "Operation Determined Path," which has kept seven of the eight major Palestinian cities under strict curfew -- reduced Internet access to a trickle in the West Bank and Gaza.
"The Israeli army stormed the office building where six (Palnet) employees were believed to be staying in order to maintain Internet service during this difficult time," the Palestinian pro-democracy group Miftah said in a statement. "Explosions were heard and the fate of the six (Palnet) employees is unknown. IDF sources verified that troops were operating in the Palnet building, but could not confirm any details of the operation.... }}}
_Originally_ from comp.risks 21.27 in 2001 (google for it - I can't be bothered to translate all the lts and gts by hand, so the followig will be munged a bit, this is the explisit mention of medireview from comp.risks 21.34)
Date: Mon, 2 Apr 2001 22:00:13 -0400 From: Kirrily Skud Robert Subject: More on Yahoo mail's anti-virus attachment translation Further to "Yahoo! Mail translates attachments" in RISKS-21.27, I saw the following e-mail on a mailing list which discusses medieval cookery: From:
Subject: (OT) "Medireview" ???
Does anyone know why certain Web sites and mail servers change the word
"medieval" to "medireview" without any warning? Have I missed something?...
So the 'original' story is only a few days less stale than the NTK one.
Early 2001, come one, get a grip. News should be _new_.
"It is a little known fact that Alpha 21064 cost more than all other 64bit CPU's at the time and performed far worse."
Show us the figures, or shut up.
The 21064, shipping in 1992 was level (Int & FP) with the PA-7150 from 1994, level to PPCs in SPECInt92 withthe 604 from 1995, but thrashed the 604 in FP.
i.e. the 21064 was _2 years_ ahead of the field.
The 21064A, shipping in 1994 was superior in Int and FP to every processor by _every_ other RISC manufacturer before 1996 apart from MIPS's R8000 from the same year, which was better at FP, but lousy at Int.
i.e. the 21064A was _nearly 2 years_ ahead of nearly the whole field.
My figures from MPR, from vendor SPEC releases.
Sure, they weren't cheap, but neither were Sparcs, or PAs.
The ding-dong battle between HP and DEC started after that, and basically DEC would spend 75% of the time top of the SPEC FP tables, but HP would always manage to throw a system into the #1 slot for about 25% of the time. Intel/AMD coming anywhere near either of those, and Power now actually beating it, are relatively new concepts considering the 10-year length of Alpha history.
PA has a segmented memory architecture, MIPS doesn't. (OK they call it an 'address space identifier', but really it's a segment, as the virtual addressing modes are all 32-bit, unlike MIPS' 64bit.) PA has packed decimal types, MIPS doesn't. PA has variable bit-field data types, MIPS doesn't. PA has 58 SP registers which can be paired for DP, MIPS has a flat DP FP register set. Both have branch delay slot but PA has optional nullification, MIPS doesn't. PA doesn't have a branch-likely extension, MIPS does. PA has conditional moves, MIPS doesn't. PA doesn't have a dingle instruction divide, MIPS does.
MIPS-III may have filled in some of the above gaps, but I stopped looking at MIPS at the MIPS-II stage.
PA was a 'braniac' design (lots per tick), MIPS was a 'speed demon' traditional RISC design (lots of ticks).
The 21064A was released in October 1993 at 275MHz, according to Bhandarkar, and went into the 3000/900 and 7000/700 systems in mid 1994. Dec didn't reach 300MHz until the release of the 21164 in Sept 1994, which reached systems in 1995. 500+MHz Alphas, such as the one I'm sitting at currently (which has not been booted into NT since about a week after I bought it, thanks to RedHat and more recently Debain), only came later.
The original Pentiums (60/66MHz) were released in 1993. They were at P6 by 1995.
So, timewise, Intel 60MHz DEC 200MHz Intel 166MHZ DEC 300MHz
You've not been to that second hand record store yet, have you?
White Rabbit, the song by Jefferson Airplane, is almost entirely Alice references.
From memory (I could google for lyrics, I guess):
"Some pills make you bigger, Some pills make you small, And the pills that mother gives you, Don't do anything at all.
Go ask Alice When she's ten feet tall.
And if you go chasing rabbits, And you know you're going to fall, Tell them a hookah-smoking catterpiller Has given you the call.
Go ask Alice, When she was just small.... "
FatPhil
Re:Praise, either way...
on
Wolframania
·
· Score: 1
If you have any recommendations for other more pithy books on the subject, aimed at a fairly bright mathematician/programmer, then please post them. After reading all the reviews, and the quotes from the book, I really can't see myself buying it any more.
Oh - Here's an anagram or three
Stephen Wolfram = Re "new math" - flops. Helps women fart
Stephen Wolfram's A new kind of science No-credence spew falsifies known math.
(Credit where credit is due - LardyGirl wrote the first, Rick Rothstein the second, and I the third.)
I said "such that it has a different value when cast to unsigned type"
You said "Typecasting isn't converting anything"
I'm glad to see you know more about the language than the standards body.
{{{ 6.3.1.3 Signed and unsigned integers
1 When a value with integer type is converted
to another integer type other then _Bool,
if the value can be represented by the new
type it is unchanged. 2 Otherwise, if the new type is unsigned, the
value is converted by repeatedly adding or
subtracting one more than the maximum value
that can be represented in the new type
until the value is in the range of the new
type. 3 [Irrelevent here]
}}}
Let me repeat that - the value is converted by repeatedly adding or subtracting...
Sheesh, slashdot is getting stupider. Please leave and do the mean IQ here a favour.
But it is a victory for webcasters! Now only a large majority will go out of business rather than all of them. Gee, it don't get any better than that, surely!
RIAA: We're too dumb to understand how technology can be used for everyone's good, so we're going to fuck 99% of you over, and get 1% of you to pay us, and keep paying us, just to let them stay alive.
is _not_ a fix. It's a total kludge. If a variable can contain a value that exceeds the range of its type, such that it has a different value when cast to unsigned type, the _the variable is of the wrong type_, and _that's_ the problem that needs to be fixed.
Slashdot Mirror
The PRP tests used to check numbers for compositeness or probable primality
actually test to see if this exponentiation procedure works.
RSA does work with carmichael numbers instead of primes, for example, because
a^c == a (mod c) for all a s.t. (a,c)==1, c a carmichael number
Try it - it works!
Phil
Firstly note that the 12 is a proven upper bound, and for the majority of
real world numbers it will be much lower.
Secondly, it's not a factoring algorithm, so your final comment is a bit odd.
Phil
These principles ignore the fact that there's a finite amount of time,
matter and energy in the universe.
A P algorithm that can never be performed due to its order or constant
factor has no practical use, only theoretical interest.
Theoretical interest is still very interesting.
Practical presses my bottons more though.
Phil
Where did you find out that they were reviewers?
However, word on teh grapevine I have access to says that it seems
that Henrik Lenstra (not to be confused with Arjen), has already
declared taht he believes the proof to be correct and elegant.
And that's about as high a recommendation as it gets.
I'll try to knock up an implementation of his algorithm some time soon, and
see what the practical big-Oh looks like.
Phil
x is just a symbol. The proof is performed using polynomial ring.
Doing shit modulo (x^r-1) means that as soon as you multiply your
polynomials together and get any terms over x^(r-1) you can replace
x^(r+d) with x^d, because (x^(r+d)-x^d) == 0 (mod (x^r-1))
e.g. modulo x^2-1
(ax+b)^2 == a^2x^2 + 2abx + b^2 == (2ab)x + (a^2+b^2)
FatPhil
I think you're missing the point of Rabin's test.
Rabin's test says that if there is no witness below 2ln^2(n), then the
number is certainly prime.
The repeated-by-a-fixed-small-number PRP-test MR test is still a
compositeness test, or a Probable Primality test, and does not give a
certain answer.
A PRP is not _proven_ prime.
See professor Caldwell's Prime Pages at:
http://primepages.org/
FatPhil
ECPP is already polynomial time with theoretical exponent ~6. However, the
best ECPP implementation out there, Marcel Martin's 'Primo', seems to behave
as if it has exponent ~4.5-5.
ECPP is non-deterministic though. But it looks like this one is too.
So this looks as if it may be worse than the state of the art.
I'll wait for Lenstra and Pomerance to say their piece though, before making
my mind up.
FatPhil
Erk, semantic minefield.
I'd say:
Difference in area is (r2^2-r1^2).pi
Ratio of areas is (r2/r1)^2
Difference of areas as a ratio is (r2^2-r1^2)/r1^2
On the whole anything that is a ratio won't have the pi term, and anything that's absolute area will have a pi term.
Phil
No, let me guess you flunked English.
Re-read your post. Reread my post. _Understand_ what I've written therein.
Then come back here apologetically when you realise that you've not just
made a minor cock-up, which was forgivable, but you've completely missed the
point being made by the person who was pointing out your mistake, and
thus made yourself look like a total fuckwit. Good darts. Double top, in fact.
FP.
It you are going to try and look clever, you'll probably want to avoid using
'whom' in utterly the wrong way.
HTH
FP.
And because it's on wiki it must be true, right? Now _that_'s naivete.
"Anonymous Cowards stick their heads up the goatse man's arse", Josef Stalin
How convincing was that? Exactly. Sheesh.
Anyway, about 12 years ago, I remember the purported quote being about
"256K", not 640K. 256K being the actual ammount of memory the top of the
range systems were being shipped with at the time.
FP
"
A decade ago, no one forsaw a need for Ghz processors, GB of RAM, Gigabit
ethernet, etc.
"
So for example in october 1988, when Arjen Lenstra and Manasse factored
the first 'hard' 100-digit number using the Multiple Polynimial Quadratic
Sieve, by spreadding the work over ~400 computers around the world, they
weren't thinking "I wish computers were ~400 times more powerful"?
I perform hard computations for a hobby - my electricity bill for my home
network is $400/year. No future processor is too powerful for me to be able
to make use of it.
FP.
Haha, why the heck have you included 3.14 in that ratio?
/repeatedly/ in this thread. Next time do it in all caps and bold too!
Do metric circles have area r^2, and imperial circles have area pi.r^2?
Funniest thing is that you've posted exactly the same flawed post
FP.
So, who's censoring whom? Let's look in today's news...
, 00 .html
...
http://www.wired.com/news/politics/0,1283,53873
{{{
Israel Blocks Palestinian ISP
By Noah Shachtman
For hundreds of thousands of Palestinians, getting to work, school or the market has been virtually impossible since Israel's latest anti-terror campaign began. Now, they won't be able to get online, either.
Early Monday morning, Israeli Defense Forces (IDF) troops took over the offices of Palnet, the leading Palestinian Internet service provider, shutting down the firm's operations. The move -- part of Israel's 3-week-old "Operation Determined Path," which has kept seven of the eight major Palestinian cities under strict curfew -- reduced Internet access to a trickle in the West Bank and Gaza.
"The Israeli army stormed the office building where six (Palnet) employees were believed to be staying in order to maintain Internet service during this difficult time," the Palestinian pro-democracy group Miftah said in a statement. "Explosions were heard and the fate of the six (Palnet) employees is unknown.
IDF sources verified that troops were operating in the Palnet building, but
could not confirm any details of the operation.
}}}
FP.
Estonia? Shome mishtake shurely?
(Estonia is Baltic, not Balkan, for a start)
FP.
_Originally_ from comp.risks 21.27 in 2001
...
(google for it - I can't be bothered to translate all the lts and gts by hand, so the followig will be munged a bit, this is the explisit mention of medireview from comp.risks 21.34)
Date: Mon, 2 Apr 2001 22:00:13 -0400
From: Kirrily Skud Robert
Subject: More on Yahoo mail's anti-virus attachment translation Further to "Yahoo! Mail translates attachments" in RISKS-21.27, I saw
the following e-mail on a mailing list which discusses medieval cookery: From:
Subject: (OT) "Medireview" ???
Does anyone know why certain Web sites and mail servers change the word
"medieval" to "medireview" without any warning? Have I missed something?
So the 'original' story is only a few days less stale than the NTK one.
Early 2001, come one, get a grip. News should be _new_.
FatPhil
"Our Alphas don't calculate much..."
:-)
Wanna donate some time to a distributed computing project?
(I'm one of the few prime-number nuts (Ernst Mayer being the other) who codes stuff for Alpha.)
FatPhil
"It is a little known fact that Alpha 21064 cost more than all other 64bit CPU's at the time and performed far worse."
Show us the figures, or shut up.
The 21064, shipping in 1992 was level (Int & FP) with the PA-7150 from 1994, level to PPCs in SPECInt92 withthe 604 from 1995, but thrashed the 604 in FP.
i.e. the 21064 was _2 years_ ahead of the field.
The 21064A, shipping in 1994 was superior in Int and FP to every processor by _every_ other RISC manufacturer before 1996 apart from MIPS's R8000 from the same year, which was better at FP, but lousy at Int.
i.e. the 21064A was _nearly 2 years_ ahead of nearly the whole field.
My figures from MPR, from vendor SPEC releases.
Sure, they weren't cheap, but neither were Sparcs, or PAs.
The ding-dong battle between HP and DEC started after that, and basically DEC would spend 75% of the time top of the SPEC FP tables, but HP would always manage to throw a system into the #1 slot for about 25% of the time. Intel/AMD coming anywhere near either of those, and Power now actually beating it, are relatively new concepts considering the 10-year length of Alpha history.
FatPhil
"PA-risc which is MIPS like"
Erm:
PA has a segmented memory architecture, MIPS doesn't. (OK they call it an 'address space identifier', but really it's a segment, as the virtual addressing modes are all 32-bit, unlike MIPS' 64bit.)
PA has packed decimal types, MIPS doesn't.
PA has variable bit-field data types, MIPS doesn't.
PA has 58 SP registers which can be paired for DP, MIPS has a flat DP FP register set.
Both have branch delay slot but PA has optional nullification, MIPS doesn't.
PA doesn't have a branch-likely extension, MIPS does.
PA has conditional moves, MIPS doesn't.
PA doesn't have a dingle instruction divide, MIPS does.
MIPS-III may have filled in some of the above gaps, but I stopped looking at MIPS at the MIPS-II stage.
PA was a 'braniac' design (lots per tick), MIPS was a 'speed demon' traditional RISC design (lots of ticks).
FatPhil
You misremember.
The 21064A was released in October 1993 at 275MHz, according to Bhandarkar, and went into the 3000/900 and 7000/700 systems in mid 1994. Dec didn't reach 300MHz until the release of the 21164 in Sept 1994, which reached systems in 1995. 500+MHz Alphas, such as the one I'm sitting at currently (which has not been booted into NT since about a week after I bought it, thanks to RedHat and more recently Debain), only came later.
The original Pentiums (60/66MHz) were released in 1993. They were at P6 by 1995.
So, timewise,
Intel 60MHz DEC 200MHz
Intel 166MHZ DEC 300MHz
Phil
You've not been to that second hand record store yet, have you?
...
White Rabbit, the song by Jefferson Airplane, is almost entirely Alice references.
From memory (I could google for lyrics, I guess):
"Some pills make you bigger,
Some pills make you small,
And the pills that mother gives you,
Don't do anything at all.
Go ask Alice
When she's ten feet tall.
And if you go chasing rabbits,
And you know you're going to fall,
Tell them a hookah-smoking catterpiller
Has given you the call.
Go ask Alice,
When she was just small.
"
FatPhil
If you have any recommendations for other more pithy books on the subject, aimed at a fairly bright mathematician/programmer, then please post them. After reading all the reviews, and the quotes from the book, I really can't see myself buying it any more.
Oh - Here's an anagram or three
Stephen Wolfram =
Re "new math" - flops.
Helps women fart
Stephen Wolfram's A new kind of science
No-credence spew falsifies known math.
(Credit where credit is due - LardyGirl wrote the first, Rick Rothstein the second, and I the third.)
FP.
I said "such that it has a different value when cast to unsigned type"
...
You said "Typecasting isn't converting anything"
I'm glad to see you know more about the language than the standards body.
{{{
6.3.1.3 Signed and unsigned integers
1 When a value with integer type is converted
to another integer type other then _Bool,
if the value can be represented by the new
type it is unchanged.
2 Otherwise, if the new type is unsigned, the
value is converted by repeatedly adding or
subtracting one more than the maximum value
that can be represented in the new type
until the value is in the range of the new
type.
3 [Irrelevent here]
}}}
Let me repeat that - the value is converted by repeatedly adding or subtracting
Sheesh, slashdot is getting stupider. Please leave and do the mean IQ here a favour.
FP.
But it is a victory for webcasters!
Now only a large majority will go out of business rather than all of them. Gee, it don't get any better than that, surely!
RIAA: We're too dumb to understand how technology can be used for everyone's good, so we're going to fuck 99% of you over, and get 1% of you to pay us, and keep paying us, just to let them stay alive.
Wankers.
FP.
From
- len_to_read = (r->remaining > bufsiz) ? bufsiz : r->remaining;
to
+ len_to_read = (r->remaining > (unsigned int)bufsiz) ? bufsiz : r->remaining
is _not_ a fix. It's a total kludge. If a variable can contain a value that exceeds the range of its type, such that it has a different value when cast to unsigned type, the _the variable is of the wrong type_, and _that's_ the problem that needs to be fixed.
This is nothing but lousy Elastoplast.
FP.