• Post Reply Bookmark Topic Watch Topic
  • New Topic

Which is faster?

 
Justin Porter
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm working with a number (count) roughly 320 bits in length, and a number (big) roughly 640 bits in length. I have both of the numbers in BigInteger form.

Now is it faster to check if 'count' is probably prime (maybe with a lower certainty parameter than 100), and then if it is, see if it is a factor of 'big', or would it just be faster to check if it is a factor of 'big' for each of them? Any comments would be appreciated, thanks!
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd bet on the latter, but to be sure I'd simply try both versions.
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13078
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With primitive ints there would be some fast checks - such as rejecting numbers with low bit = 0. I am guessing you could try rejecting all BigInteger where getlowestSetBit() != 0 - that is half your possible count values right there.
Bill
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by William Brogden:
With primitive ints there would be some fast checks - such as rejecting numbers with low bit = 0.


Isn't 2 a prime?
 
Justin Porter
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One other thing... roughly 10% of all integers are primes, correct?
 
Steven Bell
Ranch Hand
Posts: 1071
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Justin Porter:
One other thing... roughly 10% of all integers are primes, correct?


No, as Natural numbers get larger the percentage of primes tends towards, but never reaches, 0.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Steven Bell:


No, as Natural numbers get larger the percentage of primes tends towards, but never reaches, 0.


That's interesting! I would have guessed that, too, but is it proven fact?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!