Elixir on the run

Continuing with Elixir problems from exercism.io, this time something completely different 😀
It’s a variation of the chess board and grains of wheat story, and basically you need to create a function that returns the total number on the chess board, along with one that returns the number of grains on given square. Not much to it, just return 2 to the power of desired square – 1 and that’s it:

def square(number) do
  :math.pow(2, number - 1) |> round
end

So this works, but there are a few issues. And one of those is nicely mentioned in tests:

NOTE: :math.pow/2 doesn’t do what you’d expect:
`:math.pow(2, 64) == :math.pow(2, 64) – 1` is true.
It’s best to avoid functions operating on floating point numbers for very large numbers.

Also, this solution throws “(ArithmeticError) bad argument in arithmetic expression” for large numbers, e.g. 32768. So, off to seek another solution. Enum.reduce/2 to the rescue:

def square(number) do
  1..number |> Enum.reduce(fn(x, acc) -> acc * 2 end)
end

It returns correct results, but for very large numbers it is rather slow. E.g. 1.2 seconds for square(262144). So, Jim Menard offered a nice solution:

use Bitwise

def square(number) do
  bsl(1, number - 1)
end

One forgets that multiplying by 2 is equal to bit shift left operation. And, of course, there is the related Bitwise.bsl/2 method that does just that. Now the square(262144) runs as fast as square(1). Who says Elixir/Erlang isn’t fast! 😀

Advertisements
Tagged , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: