Collapse OS Documentation Browser

doc/algo.txt

asm/ code/ hw/ algo.txt arch.txt avr.txt blk.txt blksrv.txt bootstrap.txt cross.txt design.txt dict.txt dis.txt drivers.txt ed.txt emul.txt faq.txt grid.txt grok.txt impl.txt intro.txt me.txt mspan.txt ps2.txt rxtx.txt sdcard.txt sega.txt selfhost.txt spi.txt usage.txt wordtbl.txt

Algorithmic notes

Multiply a number by another

Let's say we want to multiply 6 by 5 for a result of 30.

First, let's look at binary forms:

110 ( 6 )
101 ( 5 )

The idea is that we'll loop 16 times (for 16 bit) through one of
the numbers (let's use 6), left-shifting through it. At each
step, we check if we've shifted a 1. If yes, then we add the
second number to our running result, which we also left shift
at each step.

Let's try our first (well, 13th for a 16 bit number) step. We
left-shift a 1 from 6, so we add 5 to our running result. That
gives us:

 10 ( remainder 2 )
101 ( result 5 )

Step 2, we do the same thing, left-shift a 1 again. We when left
shift our result, than add 5 to it again:

   0 ( remainder 0 )
1111 ( result 15 )

Then, for your last (16th) step, we left-shift a 0, so we don't
add anything to our result, but we still left-shift it, which
gives us our final result:

    0 ( remainder 0 )
11110 ( result 30 )

Divide a number by another, with remainder

Let's say we want to divide 249 by 7 so that we end up with
35 rem 4.

First, let's look at binary forms:

11111001 ( 249 )
     111 ( 7 )

The general idea is that we try to take the 7 and "fit" it
leftmost as much as possible so that we can subtract it. That
gives us 2 things: an order of magnitude and a remainder. Then,
we repeat until we can't do it any more.

For the first step, we can shift 7 5 times, which gives us:

11111001 ( 249 )
11100000 ( 224 )

We subtract, which gives us:

 11001 ( remainder 25 )
100000 ( quotient 32 )

Then, we fit the divisor in the remainder again:

11001 ( 25 )
 1110 ( 14 )

Which gives us:

 1101 ( remainder 11 )
10010 ( quotient 34 )

We have wiggle room for one last step:

1101 ( 11 )
 111 ( 7 )

Which gives us:

  100 ( remainder 4 )
10011 ( quotient 35 )

In terms of computing, the hard part is the "fitting". All
/MOD words in Collapse OS use the same fitting logic:

We begin with a remainder and quotient at 0 and we have a loop
that executes 16 times (for 16 bit numbers). At each step, we
left-shift the dividend into the remainder and try to subtract
the divisor from it. If it fits, we left shift a 1 into the
quotient, otherwise we left shift a 0 into the quotient.

To save space, we can even use the same memory space for the
input dividend and the output quotient because the result never
overlap while we left-shift.

Collapse OS and its documentation are created by Virgil Dupras and licensed under the GNU GPL v3.

This documentation browser by James Stanley. Please report bugs on github or to james@incoherency.co.uk.

This page generated at 2022-05-19 21:05:03 from documentation in CollapseOS snapshot 20220509.