Fwd: x**y problem 1.16 of SICP

From: lex r
Sent on: Wednesday, March 19, 2014 2:48 PM
For some reason, this email was not sent when I originally sent it on Monday  at about 1:00 pm.  I am trying again.
 
I ran this Ruby code in ideone.com and it gave correct results (e**10 is about 22000).  You may want to try rewriting these in Scheme.  Not sure how this would be done recursively, although x**y = (x**(y/2))**2 is probably involved.  (In fact, the bc command of Unix/Linux, calculates e**x by repeatedly using e**x = (e**(x/2))**2, i.e., e**10 = (e**5)**2 = ((e**2.5)**2)**2 = (((e**1.25)**2)**2)**2 = ((((e**.625)**2)**2)**2)**2,
then the series for e**x, e**x = 1 + x/1 + x**2/2! + x**3/3! + x**4/4! + ... converges very rapidly for x = .625.)
 
Just a note from a former Numerical Analyst, who has now completed 9.732 steps and should complete the program by the end of this decade.
 
Lex

---------- Forwarded message ----------
From: lex romanczuk <[address removed]>
Date: Mon, Mar 17, 2014 at 1:13 PM
Subject: x**y problem 1.16 of SICP
To: [address removed], lex romanczuk <[address removed]>


Here are 2 routines from Pascal User Manual and Report - Jensen/Wirth to find x**y where x is int/float and y is integer >= 0.  I added a third routine, a modification that uses base 3 instead of base 2 so you may get more understanding of what is happening (i.e., the exponent is just being written in base 2, or base 3 or whatever, as we learned to do in grade school by repeated division by the base (2, 3, 8, 16 whatever) and getting the remainders.
 
The are written in Ruby, because I couldn't get Scheme to  work on
 
Lex
 
#Function power(x, y) = x**y raises a real value x to the integer power y >= 0
#Pascal User Manual and Report, Kathleen Jensen, Niklaus Wirth
def power1(x, y) #Exponent found in base 2
  z, b, e = 1.0, x, y
  while e > 0 do #{z*(b**e) = x**y}
    z = z * b if e & 1 == 1
    e >>= 1; b *= b
    end
  return z #{z = x**y}
  end
def power2(x, y) #Exponent found in base 2
  z, b, e = 1.0, x, y
  while e > 0 do #{z*(b**e) = x**y}
    while e & 1 == 0 do
      e >>= 1; b *= b
      end
    e -= 1; z *= b
    end
  return z #{z = x**y}
  end
def power3(x, y) #Exponent found in base 3
  z, b, e = 1.0, x, y
  while e > 0 do #{z*(b**e) = x**y}
    while e % 3 == 0 do
      e /= 3; b *= b*b
      end
    e -= 1; z *= b
    end
  return z #{z = x**y}
  end
puts power[masked], 10)
puts power[masked], 10)
puts power[masked], 10)

 

Our Sponsors

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy