埃及乘法算法

https://weread.qq.com/web/reader/3b732670813ab99bag015817#outline?noScroll=1

从小学时代开始，我们都知道, $a \times b = \sum_{i=0}^{b} a$

但是我们实际在计算 $41 \times 59$ 的时候，肯定不会傻傻的计算41次求和。

古埃及人很早就发现了乘法计算的方式，当他们在计算 $n \times a$

每次都把a翻倍，然后把n减半。

这里的思路跟快速幂是一样的

41 = (101010)_2

用递归可以很快把代码写出来

defmodule DemoEgyptMath do
  import Bitwise

  @moduledoc """
  Documentation for `DemoEgyptMath`.
  """

  @spec multiply(integer, integer) :: integer
  def multiply(n, a) do
    case {n, a} do
      {1, _} -> a
      _ -> multiply(0, n, a)
    end
  end

  defp multiply(r, n, a) do
    case {n, a} do
      {0, _} -> r
      {n, a} -> multiply(if(is_odd(n), do: r + a, else: r), divide_by_2(n), a + a)
    end
  end

  @spec is_odd(integer) :: boolean
  def is_odd(n) do
    (n &&& 1) == 1
  end

  def divide_by_2(n) do
    n >>> 1
  end
end

这里用了位运算来简化操作