SM-3a-VariousElementaryAlgorithms

4316 days ago by nhanbaoho

Before we investigate some of the more advanced uses of Sage (as advanced of uses in which I, in my novicehood, feel comfortable guiding us), let's take a look at what some of the "classic" algorithms look like in Sage. To start with, there's that old stand-by:
print "Hello, world!" 
        
Hello, world!
Hello, world!
Nearly as simple is everyone's favorite exercise from CS 101, an implementation of the factorial function (of course, Sage has its own built-in implementation):
def fact(n): if n == 0 or n == 1: return 1 else: return fact(n-1)*n fact(10);fact(11) 
        
3628800
39916800
3628800
39916800
Who among us hasn't written her or his fair share of Fibonacci sequence generators?:
def fibs(n): f = [1,1] i = 2 while i<n: f.append(f[i-1]+f[i-2]) i = i+1 return f fibs(10) 
        
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
fibs(50) 
        
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976,
7778742049, 12586269025]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]
Maybe a a little more obscure is the ever-popular QuickSort algorithm:
n = 100 listSize=25 rands = [floor(random()*n+1) for i in [1..listSize]] def quicksort(aList): theList = aList if len(theList)==1: return theList else: early = [] late = [] pivot=floor(random()*len(theList)) pivotValue=theList[pivot] del theList[pivot] for j in [0..len(theList)-1]: if theList[j]<pivotValue: early.append(theList[j]) else: late.append(theList[j]) if len(early)>=1: sortEarly = quicksort(early) else: sortEarly = [] if len(late)>=1: sortLate = quicksort(late) else: sortLate = [] sortEarly.append(pivotValue) for j in [0..len(sortLate)-1]: sortEarly.append(sortLate[j]) return sortEarly print(rands) quicksort(rands) 
        
[99, 33, 35, 60, 91, 92, 26, 37, 49, 74, 73, 78, 19, 68, 82, 57, 18, 69,
22, 3, 86, 61, 55, 87, 96]
[3, 18, 19, 22, 26, 33, 35, 37, 49, 55, 57, 60, 61, 68, 69, 73, 74, 78,
82, 86, 87, 91, 92, 96, 99]
[99, 33, 35, 60, 91, 92, 26, 37, 49, 74, 73, 78, 19, 68, 82, 57, 18, 69, 22, 3, 86, 61, 55, 87, 96]
[3, 18, 19, 22, 26, 33, 35, 37, 49, 55, 57, 60, 61, 68, 69, 73, 74, 78, 82, 86, 87, 91, 92, 96, 99]
In all of the above we've made heavy use of Sage's basic control structures, precisely those which are present in the Python programming language, that from which Sage is itself derived. Sage, however, has capabilities beyond stripped-down Python, capabilities that make it the rival of its more well-known commercial cousins, Mathematica and Maple. After all, not every programming language will give us the functionality to evaluated the gamma function:
def gamma(n): return integral(x^(n-1)*e^(-x), x, 0, infinity) facts=[gamma(n) for n in [1..10]] print facts 
        
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
gamma(pi).n(digits=10) 
        
2.288037795
2.288037795