Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2013

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Russian Peasant Multiplication / was question on

  • To: mathgroup at smc.vnet.net
  • Subject: [mg131368] Re: Russian Peasant Multiplication / was question on
  • From: Bob Hanlon <hanlonr357 at gmail.com>
  • Date: Mon, 1 Jul 2013 05:51:59 -0400 (EDT)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • Delivered-to: l-mathgroup@wolfram.com
  • Delivered-to: mathgroup-outx@smc.vnet.net
  • Delivered-to: mathgroup-newsendx@smc.vnet.net
  • References: <kqm6u7$hp5$1@smc.vnet.net>

Clear[russianPeasantMultiply];


russianPeasantMultiply[
   x_Integer, y_Integer] :=
  Sign[x]*Sign[y]*
   Total[
    Cases[
      NestWhileList[
       Floor[{1/2, 2}*#] &,
       Sort[Abs[{x, y}]],
       (First[#] > 1) &],
      {_?OddQ, _}][[All, -1]]];


m = 10^6;
x = RandomInteger[{-m, m}];
y = RandomInteger[{-m, m}];


russianPeasantMultiply[x, y] == x*y

True



Bob Hanlon


On Sun, Jun 30, 2013 at 3:29 AM, <d.a.paxton at gmail.com> wrote:

> On Saturday, June 29, 2013 2:47:03 AM UTC-6, Richard Fateman wrote:
> > Dave --
> >
> > 1.  You should try to come up with a useful subject line
> >
> > in the future.
> >
> > 2. It is called Russian Peasant Multiplication (which you may
> >
> > find on Google).
> >
> > 3. There is no reason to believe that a procedural algorithm
> >
> > has a formula, but in this case I think the inverse is known
> >
> > as division :)
>
> I am sorry for posting a question that is improper.  It is a matter of
> rounding as a floor or ceiling question I guess wondering nomenclature.  If
> the lowest count on the numbers in a multiply are let's say 7 and 5.  We
> multiple these and get 35.  How does on drop the 5 into the lowest of the
> answer and carry the 3?  Since 7 and 5 and also 35 are know known we do
> this..  In base ten we multiply by ten.  Divide out the seven and get
> fifty.  Divide that by ten and get the 5 drop out number.  Then put the the
> thirty five minus the drop out number and then divide by ten again.  Gives
> three.  The carry number.  So I guess in using this for any base number
> system we do have a divide as an inverse function for any variables in the
> course of a multiply.
>
>




  • Prev by Date: Re: What is f[1]? Advanced question
  • Next by Date: Re: Complex path integral wrong
  • Previous by thread: Re: What is f[1]? Advanced question
  • Next by thread: Re: Russian Peasant Multiplication / was question on