Calculating the largest known prime in Ruby | Hacker News Reader

Calculating the largest known prime in Ruby

jpcamara.com

23 pointsthunderbong10 comments

Nice. You can do the same in Python like so and surprisingly it only takes a couple seconds to a minute to get the print out, no need for importing any special libraries (just `sys` to enable printing large numbers).

```python

import sys sys.set_int_max_str_digits(0) # Allows for printing very large numbers.

x = (2 * 136_279_841) - 1

print(x)

```

Use two leading spaces to create monospaced code on this site, like so:

  import sys
  sys.set_int_max_str_digits(0) # Allows for printing very large numbers
  x = (2 ** 136_279_841) - 1
  print(x)

Also, note that 1 << 136_279_841 is much faster than 2 ** 136_279_841; the former runs in <10ms, while the latter takes over 600ms on my machine (a 60x difference).

Could explain the << calculation a bit? I read about the operator but it’s not clear how this works

It means "left shift" in binary. This corresponds to adding a specified number of zeros at the end of the binary representation of the original number. So 1 << 0 is binary 1, 1 << 1 is binary 10, 1 << 2 is binary 100, 1 << 3 is binary 1000...

If you think about the meaning of place value in binary, this is exactly the same as raising two to a specified power. Each time you shift one place further left in binary, it's equivalent to multiplying the existing number by two. So repeating that a specified number of times is multiplying by a specified power of two.

Shifting an integer left `n` bits is equivalent to multiplying it by `2 ** n`

1 is 2 to the power 0 ... 0b0001

shifted left once, it becomes 2 to the power 1 ... 0b0010

shifted left twice, it becomes 2 to the power 2 ... 0b0100

shifted left three times, it becomes 2 to the power 3 ... 0b1000

etc until

shifted left 136_279_841 times, it becomes 2 to the power 136_279_84 ... 0b1000...many zeros...0000

subtract 1, it becomes

0b0111...many ones...1111

One funny thing about Mersenne primes is that, as a result of what you describe, they are exactly those primes whose binary representation consists of a prime number of ones!

The smallest Mersenne prime, three, is binary 11, while the next largest is seven (111), then 31 (11111), then 127 (1111111). The next candidate, 2047 (11111111111), is not prime.

I've been told that Ruby was the slowest language of the universe, much more than Python. That's interesting challenge!

I think that reputation stem from Ruby 1.X era, Ruby is now at 3.X which have had massive improvements on the performance (for being an interpreted language).

Sounds like a new possible attack vector?

Reply on news.ycombinator.com