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:
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)
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)
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)
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