Very recently a saw a Youtube video from a friend, MathGurl, in which she explained the ancient Egyptian multiplication method. At the same time, and for no particular reason, I remembered Haskell, so I decided to implement the method. It was not a big feat of programming, but I did enjoy relearning the basics of Haskell I once knew. You can find the file with the implementation here.
(The implementation only works for non-negative integers)
The method is quite simple and works because of the binary expansion of a number. Basically, if you want to calculate a * b, either b is even or odd. If b is even, just cut b in half and duplicate a to compute (2a)(b/2). If b is odd, then ab = a + (2a)*((b-1)/2). Another way of thinking about this is by writing b in the form b = 2^(k_1) + 2^(k_2) + ... + 2^(k_n) and then having ab = a(2^(k_1) + 2^(k_2) + ... + 2^(k_n)) = a2^(k_1) + a2^(k_2) + ... + a2^(k_n). My formulation is just the recursive way of writing it.
If I get the courage to do it, I might also redo the functions in the Kleene Recursion post again, in Haskell...
[Pt] Há pouco tempo vi este vÃdeo da MathGurl sobre a multiplicação egÃpcia ao mesmo tempo que me lembrava da existência de Haskell, e portanto decidi fazer esta implementação do método (que só funciona para números não negativos). Para quem não conhecer o método, aconselho o vÃdeo!
Se tiver coragem, um dia destes refaço as funções do post sobre a recursão de Kleene em Haskell...
Let me know what you think!
-RGS
(The implementation only works for non-negative integers)
The method is quite simple and works because of the binary expansion of a number. Basically, if you want to calculate a * b, either b is even or odd. If b is even, just cut b in half and duplicate a to compute (2a)(b/2). If b is odd, then ab = a + (2a)*((b-1)/2). Another way of thinking about this is by writing b in the form b = 2^(k_1) + 2^(k_2) + ... + 2^(k_n) and then having ab = a(2^(k_1) + 2^(k_2) + ... + 2^(k_n)) = a2^(k_1) + a2^(k_2) + ... + a2^(k_n). My formulation is just the recursive way of writing it.
If I get the courage to do it, I might also redo the functions in the Kleene Recursion post again, in Haskell...
[Pt] Há pouco tempo vi este vÃdeo da MathGurl sobre a multiplicação egÃpcia ao mesmo tempo que me lembrava da existência de Haskell, e portanto decidi fazer esta implementação do método (que só funciona para números não negativos). Para quem não conhecer o método, aconselho o vÃdeo!
Se tiver coragem, um dia destes refaço as funções do post sobre a recursão de Kleene em Haskell...
Let me know what you think!
-RGS
Egyptian multiplication with Haskell
![Egyptian multiplication with Haskell]()
Reviewed by Unknown
on
October 25, 2017
Rating:
No comments: