type javascript: maximum element random list linear search binary search bubble sort convert base modular exponentiation greatest common divisor prime factorization factorial recursion fibonacci numbers combinations random matrix matrix multiplication	timing: s
// Find the maximum value in a list of numbers max = function(a) { var m = a[0]; for (var i = 1; i < a.length; i++) { writeln("m = "+m); if (m < a[i]) m = a[i]; } return m; } a = random_list(6,1,10); writeln(a); max(a);

// Find the maximum value in a list of numbers max = function(a) { var m = a[0]; for (var i = 1; i < a.length; i++) { writeln("m = "+m); if (m < a[i]) m = a[i]; } return m; } a = random_list(6,1,10); writeln(a); max(a); // Construct a list of n random integers from r to s // random() returns a uniformly distributed random number in [0,1) random_list = function(n, r, s) { var a = []; for (var i = 0; i < n; i++) { a[i] = floor(random()*(s-r+1)) + r; } return a; } random_list(100,1,10) // Find first occurrence of an element in a list of numbers linear_search = function(x,a) { var i = 0; while (i < a.length && x != a[i]) { writeln("i = "+i); i = i+1; } if (i < a.length) return i; else return "not found"; } a = random_list(6,1,10); writeln(a); linear_search(3,a); // Find first occurrence of an element in a *sorted* list of numbers binary_search = function(x,a) { var i = 0; // i is the left endpoint of the search interval var j = a.length-1; // j is the right endpoint of the search interval while (i < j) { writeln("i="+i+", j="+j); m = floor((i+j)/2); if (x > a[m]) i = m+1; else j = m; } if (x == a[i]) return i; else return "not found"; } binary_search(3, [1,2,2,2,3,3,4,5,6,7,8]); // Sort a list of numbers using (inefficient) bubble sort bubble_sort = function(a) { var t; for (var i = 0; i < a.length-1; i++) for (var j = 0; j < a.length-i; j++) if (a[j] > a[j+1]) { writeln("swap "+a[j]+", "+a[j+1]); t = a[j]; a[j] = a[j+1]; a[j+1] = t; } return a; } a = random_list(6,1,10); writeln(a); bubble_sort(a); // Convert a positive base 10 integer to another base convert = function(n,b) { var m = []; while (n > 0) { m = [n % b].concat(m); n = floor(n/b); } return m; } convert(123456789,5); // Calculate the n-th power mod m efficiently powermod = function(b,n,m) { var x = 1; var p = b % m; while (n > 0) { if (n%2 == 1) x = (x*p) % m; p = (p*p) % m; n = floor(n/2); writeln("n = "+n+", x = "+x); } return x; } powermod(123456789, 543, 12345); // Find the greatest common divisor of two positive integers // using the Euclidean algorithm gcd = function(a,b) { var r; while (b > 0) { writeln("a = "+a+", b = "+b); r = a % b; // remainder a = b; b = r; } return a; } gcd(49,84); //gcd(fibonacci(15),fibonacci(14)); // Find the prime factors of a positive integer (inefficiently) primefactors = function(n) { var p = 2; var a = []; while (p*p <= n) { if (n%p == 0) { n = floor(n/p); writeln(n*p+" = "+p+" * "+n); a = a.concat([p]); } else p = p+1; } return a.concat([n]); } primefactors(1234567891011); //primefactors(2*3*5*7*11*13 + 1); //primefactors(123456789123451); // Calculate the factorial of a natural number using recursion factorial = function(n) { // simple version if (n <= 0) return 1; else return n*factorial(n-1); } factorialw = function(n) { // write intermediate results var k; if (n <= 0) return 1; else { writeln("n = "+n); k = n*factorialw(n-1); writeln("k = "+k); return k; } } factorialw(10); // Calculate the n-th Fibonacci number iteratively fibonacci = function(n) { var a = 0; var b = 1; for (var i=0; i<n; i++) { write(a+" "); b = a+b; a = b-a; } writeln("\n"); return a; } fibonacci(50); // Calculate the binomial coefficient C(n,k) C = function(n,k) { var c = 1; for (var i=1; i<=k; i++) { writeln("c = "+c); c = c*(n-k+i)/i; } return c; } C(50,20); // Construct a matrix of m x n random integers from r to s random_matrix = function(m, n, r, s) { var A = []; for (var i = 0; i < m; i++) { A[i] = []; for (var j = 0; j < n; j++) A[i][j] = Math.floor(Math.random()*(s-r+1)) + r; } return A; } random_matrix(3,3,0,4) // multiply two matrices mult = function(A,B) { var C = []; for (var i = 0; i < A.length; i++) { C[i] = []; for (var j = 0; j < B[0].length; j++) { C[i][j] = 0; for (var k = 0; k < A[0].length; k++) C[i][j] = C[i][j] + A[i][k]*B[k][j]; } } return C; } A = random_matrix(3,3,0,4); writeln(A) B = random_matrix(3,3,0,4); writeln(B) mult(A,B)