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);
}

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;
}