Miscellaneous Code Examples

Swap

You can swap two numbers using a, b = b, a;

#import "Basic";

main :: () {
    a := 5;
    b := 9;

    print("Before swap: a = %, b = %\n", a, b);
    a, b = b, a;
    print("After swap:  a = %, b = %\n", a, b);
}

Perfect Numbers

A perfect number is an integer that is equal to the sum of its positive proper divisors, that is, divisors excluding the number itself. For instance, 6 has proper divisors 1, 2, and 3, and 1 + 2 + 3 = 6, so 6 is a perfect number. The next perfect number is 28, because 1 + 2 + 4 + 7 + 14 = 28.

We can create a function to determine if a number is perfect or not. Add up all the factors of the number, and if the sum of all factors is equal to the number, then return true.

#import "Basic";

is_perfect :: (n: int) -> bool {
    if n <= 1 return false;

    sum := 1;
    for i: 2..n/2 + 1 {
        if n % i == 0 {
            sum += i;
        }
    }

    return sum == n;
}

main :: () {
    for i: 1..10000 {
        if is_perfect(i) {
            print("% is a perfect number.\n", i);
        }
    }
}

XOR Swap

The XOR swap is an algorithm that uses the XOR bitwise operation to swap the values of two variables without using the temporary variable which is normally required.

#import "Basic";

main :: () {
    a := 5;
    b := 9;

    print("Before swap: a = %, b = %\n", a, b);

    // XOR swap
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

    print("After swap:  a = %, b = %\n", a, b);
}

Shuffle an Array

This is some code to shuffle an array using the Fischer-Yates shuffle algorithm. One can define a random_s64 function to make the casting to make the code more aesthetically pleasing to read.

random_s64 :: () -> s64 {
    r := (random_get() & 0x7FFF_FFFF);
    return cast(s64)r;
}

shuffle :: (array: [] int) {
    N := array.count - 1;
    for < i : 1..N {
        r := random_s64() % i;
        array[i], array[r] = array[r], array[i];
    }
}

Here is a while loop version of the code:

shuffle :: (array: [] int) {
    i := array.count - 1;
    while i >= 1 {
        r := random_s64() % i;
        array[i], array[r] = array[r], array[i];
        i -= 1;
    }
}

Popcount

This algorithm performs a popcount based off of Brian Kernighan's algorithm. One only considers the set bits of an integer. One turns off the rightmost set bit after counting it, and we iterate until no more bits are left. The expression n-1 flips all the bits after the rightmost set bit of n, including the rightmost set bit itself.

popcount :: (number: u64) -> int {
    result := 0;
    while number != 0 {
        result += 1;
        number &= (number - 1);
    }
}

Palindrome

A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards. This is a function to compute whether a string is a palindrome.

#import "Basic";
#import "String";

is_palindrome :: (s: string) -> bool {
    left := 0;
    right := s.count - 1;

    while left < right {
        if s[left] != s[right] return false;
        left += 1;
        right -= 1;
    }

    return true;
}

main :: () {
    words := string.[ "racecar", "hello", "level", "banana", "madam" ];

    for word: words {
        if is_palindrome(word)
            print("\"%\" is a palindrome.\n", word);
        else
            print("\"%\" is not a palindrome.\n", word);
    }
}

Bit Scan Forward

A bit scan forward implementation using De Bruijn Multiplication based off of this implementation.

index64 :: int.[
     0,    1,   48,    2,   57,   49,   28,    3,
    61,   58,   50,   42,   38,   29,   17,    4,
    62,   55,   59,   36,   53,   51,   43,   22,
    45,   39,   33,   30,   24,   18,   12,    5,
    63,   47,   56,   27,   60,   41,   37,   16,
    54,   35,   52,   21,   44,   32,   23,   11,
    46,   26,   40,   15,   34,   20,   31,   10,
    25,   14,   19,    9,   13,    8,    7,    6,
];

bit_scan_forward :: (value: u64) -> int {
    DEBRUIJN64 : u64 : 0x03f79d71b4cb0a89;
    value = value & (cast,no_check(u64) -(cast(int)value));
    return index64[ (value * DEBRUIJN64) >> 58];
}

Euclidean Algorithm to find Greatest Common Denominator

GCD using Subtraction

This code performs GCD using recursion. This is a subtraction-based method to find the GCD and will help you find the GCD of two numbers, a and b.

gcd :: (a: int, b: int) -> int {
    // Everything divides 0
    if a == 0 {
        return b;
    }

    if b == 0 {
        return a;
    }

    // base case
    if a == b {
        return a;
    }

    // a is greater
    if a > b {
        return gcd(a - b, b);
    }

    return gcd(a, b - a);
}

GCD using Modulo

A more efficient version uses modulo instead of subtraction as it reduces the steps to a fewer number of steps.

gcd :: (a: int, b: int) -> int {
    // Base case, if the second number becomes 0, the first number is the GCD
    if b == 0 {
        return a;
    }

    // Recursive step to call gcd with the smaller pair
    return gcd(b, a % b);
}

GCD using Iterative Method

We can perform the same recursive function using iterative methods.

gcd :: (a: int, b: int) -> int {
  r := 0;
  while ((a % b) > 0)  {
    r = a % b;
    a = b;
    b = r;
  }

  return b;

}

Pi Calculation

This piece of code computes the value of Pi using the Leibniz Formula.

compute_pi :: () -> float {
  // calculate pi using the leibniz formula.
  n := 1.0;
  s := 1.0;
  pi := 0.0;

  for 0..10000 {
    pi +=  1.0 / (s*n);
    n += 2.0;
    s = -s;
  }
  return pi*4.0;
}

Newton Square Root Calculation

Newton's method (also known as the Newton-Raphson method) is an efficient way to calculate square roots iteratively.

newton_sqrt :: (number: float, epsilon: float) -> float {
    assert(number >= 0.0);
    if (number == 0) {
        return 0.0;
    }

    x := number; // Initial guess
    previous: float;

    while abs(x - previous) > epsilon {
        previous = x;
        x = 0.5 * (x + number / x); // Newton's method formula
    }

    return x;
}