• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Devaka Cooray
  • Ron McLeod
  • paul wheaton
Saloon Keepers:
  • Tim Moores
  • Piet Souris
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Frits Walraven
  • Scott Selikoff

Which is faster?

 
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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!
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'd bet on the latter, but to be sure I'd simply try both versions.
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
One other thing... roughly 10% of all integers are primes, correct?
 
Ranch Hand
Posts: 1071
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
We can walk to school together. And we can both read this tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic