TDWTF: Russian Peasant Multiplication

[Kirill]

Please see this post: Russian Peasant Multiplication

It ends with:

Your challenge: write a function that multiplies two numbers using the Russian peasant algorithm. There is no language restriction, though anything on the esoteric language list will probably be ignored. Spoiler alert: the solution(s) will undoubtedly appear in the comments.

There is no LISP solution there yet...

[cormullion]

You can find Lutz' (I assume!) typically elegant solution there now.

[xytroxon]

You can find Lutz' (I assume!) typically elegant solution there now.

Re: Programming Praxis: Russian Peasant Multiplication
2009-07-22 14:51 • by newlisp.org (unregistered)

278283 in reply to 277861
Reply Quote
improvement for some problems starting with even number:

Code: Select all

(define (rmul x y , (s 0))

  (until (= x 1)

    (unless (zero? (% x 2))

      (inc s y))

    (setq x (>> x) y (<< y)))

  (+ y s)

)

I think I found it... 9 pages of code entries posted so far? Al Gore won't be very happy over all the CO2 generated ;)

-- xytroxon

[TedWalther]

You can find Lutz' (I assume!) typically elegant solution there now.

Thanks for the link. I was so inspired, I dashed off this one-liner:

Code: Select all

(define (rmul x y) (if (= x 1) y (+ (if (zero? (% x 2)) 0 y) (rmul (>> x) (<< y)))))

Ted

[newdep]

I think I found it... 9 pages of code entries posted so far? Al Gore won't be very happy over all the CO2 generated ;)

I think I all people on this planet would stop talking for 1 day we solved the CO2 problem already..thats including Al.. ;-)


I Like these brain trainers.. But Cormullion posted already the trick...<<iekss>>..now I need to wait for another one to come by.. I was too quick in clicking..;-)

[TedWalther]

Here is the same solution, but with more normal indenting. Still ends up being 6 line, like Lutz' solution, but uses tail recursion and maybe does fewer assignments?

Code: Select all

(define (rmul x y)
  (if (= x 1)
      y
    (+
     (if (zero? (% x 2)) 0 y)
     (rmul (>> x) (<< y)))))

[TedWalther]

Even better, the even? predicate could be written like this:

Code: Select all

(= (& x 1) 0)

I really wish that 0 could be included as a value for "false" in numeric contexts. That is the one thing from C and other languages that I miss.

I often find myself wishing that "" and 0 as well as nil were counted as false values.

Ted

[TedWalther]

Desired False values:
0 (integer or float)
"" (empty string)

Current False values:
false (symbol)
nil (symbol)
() (empty list)

I do know that there are reasons for not allowing "" or 0 as false values. Can someone fill me in? As a former C programmer, I find them very comfortable idioms.

Ted

[TedWalther]

Even shorter version of the russian peasant:

Code: Select all

(define (rmul x y)
  (if (= x 1)
      y
    (+ 
     (* (& x 1) y)
     (rmul (>> x) (<<y)))))

[TedWalther]

accidentical duplicate, please delete this post.

[Lutz]

I do know that there are reasons for not allowing "" or 0 as false values. Can someone fill me in? As a former C programmer, I find them very comfortable idioms.

try 'null?' which combines nil?, empty? and zero?

Code: Select all

(map null? '(() nil "" 0 0.0)) => (true true true true true)

ps: note that 'false' is not a built-in symbol, it only works, if nobody has set it.

ps2: maintenance release 10.1.1 is on its way

[TedWalther]

Thanks Lutz. Maybe I'll start using (if-not-null ...) in my code now. Not as satisfying as a straight (if) statement, not as impressive in a code contest like the russian peasant one, but it will work. Are there reasons somewhere for not having (not (null? ..)) as the default for (if, or, and, case) and relatives? Just LISP tradition? I did read a JavaScript book by a LISP guy where he was really negative about that very feature of JavaScript, but I couldn't quite make out why he thought it was a bad feature.

Ted

I do know that there are reasons for not allowing "" or 0 as false values. Can someone fill me in? As a former C programmer, I find them very comfortable idioms.

try 'null?' which combines nil?, empty? and zero?

Code: Select all

(map null? '(() nil "" 0 0.0)) => (true true true true true)

ps: note that 'false' is not a built-in symbol, it only works, if nobody has set it.

ps2: maintenance release 10.1.1 is on its way