6 ms·

Firstly, the number of prime numbers < n grows by roughly n/log(n) So moving from 2^16 = 65536 to 2^32 = 4294967296 Increases the size of the total potentia

Firstly, the number of prime numbers < n grows by roughly n/log(n) So moving from 2^16 = 65536 to 2^32 = 4294967296 Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769 secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part. if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Thirdly, your stupidly high costs are because you seem to think you need to check if 4817 x 5693 is a prime fractorisation of 26768069 when in fact you already know the prime factorisation by that point.

littlestymaar 2y ago
> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 “The earth is flat blah blah blah”
- DarkmSparks 2y ago
  opposing side of an argument resorting to a strawman is their implicit admission they were wrong.
  - jedwards1211 2y ago
    We're trying to help you understand, and you're stubbornly refusing to swallow your pride and think about what we're saying
bmacho 2y ago
> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Can you answer a) If 1 apple costs you 8$ then (1)^2 apple costs you: ??? b) If 10 apples cost you 8$ then (10)^2 apples costs you: ??? edit: between the price and the amount, usually there is a ~linear relationship. So if you can buy 2^512 something for 8$, then chances are that for 8 times the price you'll only get ~8 times more amount, and not 2^512 times more
- DarkmSparks 2y ago
  the ^2's are https://en.m.wikipedia.org/wiki/Big_O_notation https://en.m.wikipedia.org/wiki/Big_O_notation The tldr is bigO gives you how the cost of apples changes with the number of apples in the worst case. its a rough simplification, the precise formula is close but not exactly that. the simplification is also actually (2n)^2 but in my defense I was going from memory of work from more than 2 decades ago (testing generated prime factors were good prime factors, overwhelmingly they were not). using your apples example if the bigO of eating apples is O(n^2), and it takes you 8 minutes to eat 2 apples, it will take you no more than 64 minutes to eat 4 apples.
jedwards1211 2y ago
Okay I hadn't read about how many calculations it takes to cover the search space, so my equations aren't right about that. However, you will do yourself a big favor if you take the time to understand why this is wrong: > if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 The cost per calculation is some constant C: Cost(n calcs) = n calcs * C Therefore, Cost(n^2 calcs) = n^2 calcs * C In this example, C = $8 / 2^512 = $2^-509 So Cost(2^512^2) = Cost(2^1024) = 2^1024 * $2^-509 = $2^425
- DarkmSparks 2y ago
  I wouldnt argue with a claim of $2425 tbh. The $8 will vary, and the actual cost function completely depends on the implimentation, its definitely possible to do worse, very likely possible to do better - there was rumors a few years ago that some Riemann surface based math can do it in O(1), but I know nothing about Riemann surfaces so can't judge their veracity.

littlestymaar 2y ago

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 “The earth is flat blah blah blah”

DarkmSparks 2y ago
opposing side of an argument resorting to a strawman is their implicit admission they were wrong.
- jedwards1211 2y ago
  We're trying to help you understand, and you're stubbornly refusing to swallow your pride and think about what we're saying

bmacho 2y ago

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Can you answer a) If 1 apple costs you 8$ then (1)^2 apple costs you: ??? b) If 10 apples cost you 8$ then (10)^2 apples costs you: ??? edit: between the price and the amount, usually there is a ~linear relationship. So if you can buy 2^512 something for 8$, then chances are that for 8 times the price you'll only get ~8 times more amount, and not 2^512 times more

DarkmSparks 2y ago
the ^2's are https://en.m.wikipedia.org/wiki/Big_O_notation https://en.m.wikipedia.org/wiki/Big_O_notation The tldr is bigO gives you how the cost of apples changes with the number of apples in the worst case. its a rough simplification, the precise formula is close but not exactly that. the simplification is also actually (2n)^2 but in my defense I was going from memory of work from more than 2 decades ago (testing generated prime factors were good prime factors, overwhelmingly they were not). using your apples example if the bigO of eating apples is O(n^2), and it takes you 8 minutes to eat 2 apples, it will take you no more than 64 minutes to eat 4 apples.

jedwards1211 2y ago

Okay I hadn't read about how many calculations it takes to cover the search space, so my equations aren't right about that. However, you will do yourself a big favor if you take the time to understand why this is wrong: > if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 The cost per calculation is some constant C: Cost(n calcs) = n calcs * C Therefore, Cost(n^2 calcs) = n^2 calcs * C In this example, C = $8 / 2^512 = $2^-509 So Cost(2^512^2) = Cost(2^1024) = 2^1024 * $2^-509 = $2^425

DarkmSparks 2y ago
I wouldnt argue with a claim of $2425 tbh. The $8 will vary, and the actual cost function completely depends on the implimentation, its definitely possible to do worse, very likely possible to do better - there was rumors a few years ago that some Riemann surface based math can do it in O(1), but I know nothing about Riemann surfaces so can't judge their veracity.