amacgillivray

Solving Perfect Numbers Quickly with Haskell

Walking through the stages of optimizing a perfect-number algorithm; starting with a naive approach, rewriting to use the Euclid-Euler theorem, and then leveraging the Miller-Rabin primality test.

A Frustratingly Naive Solution

On a dark and stormy night in Kansas, many years ago, I sat in front of my laptop - face lit only by the screen.

A homework assignment had tasked us with writing a basic haskell function to find every perfect number between 1 and 9000. We weren't studying numbers, nor did we discuss perfect numbers in class. The number "9000" was chosen as the upper limit due to the complexity associated with finding perfects using typical methods.

amacgillivray

When I encountered Leetcode's Divide Two Integers problem, I immediately remembered the MIPS architecture and various ALU implementations I did in verilog for my CS classes. I heavily referenced this document on ALU Division Design, and used it to guide my C++ implementation.

This turned out to be a really straightforward solution to implement, and somewhat different than the solution recommended on Leetcode's "Editorial" tab. Let's see how it works.

Understing MIPS-Style ALU Division

Lets say we are doing this division on a system that uses 5-bit integers:

dividend = 20; // 0b10100

amacgillivray

FISR to find Sqrt(x)

...in rust

This is another fun/interesting toy problem based on a leetcode question.

In this case, the question asks for a function that can find the square root of an integer:

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.