Integer arithmetic for space age

Exercism
1

@ErikSchierboom I have uploaded a couple more MIPS exercises for review.

One of them is Space Age. Instead of using floating point, I request the answer in hundredths of a year.

My example solution might be interesting for video: multiplying by reciprocal instead of using a division instruction.

Two of the standard test cases have answers in years that are a little close to the rounding cutoffs, where if we using thousandths the last digit would be 4 or 6. My suggestion is to adjust these test cases a little, so more students will be able to pass the tests. (Another option would be allow solutions off by a hundredth for these test cases.)

1 Like
2

That’s perfectly fine!

3

All approved, with one comment on the space-age PR.

4

Ping me when it is published :)

5

Published

6

Great. Could you maybe explain how the reciprocal works? I have a general understanding, but don’t entirely understand it yet.

7

To check precision, we can use the following pair of examples:

2147419572 seconds is 282.53499 Mercury years, rounding to 28253 Mercury centi-years.
2147419724 seconds is 282.53501 Mercury years, rounding to 28254 Mercury centi-years.

An Earth centi-year is 315576 seconds, so a Mercury centi-year is 0.2408467 × 315576 ≈ 76005.4382 seconds.

What happens when we use integer division by 76005?

2147419572 ÷ 76005 gives 28253, remainder 50307
2147419724 ÷ 76005 gives 28253, remainder 50459
We might round the answers up because the remainders exceed half of 76005. Either way, one of the answers won’t be ideal.

The problem is with 76005, we are only using 17 bits of precision.

Instead of dividing, can we multiply by 1/76005.4382 ?

To use integer arithmetic, we will need to scale up 1/76005.4382 by some 2^n, and then remove the bottom n bits from the multiplication result.

Let’s try n=48

2^48 * 1/76005.4382 = 3703353120

This fits in 32 bits, provided we use unsigned arithmetic.

We don’t have negative ages in space customs forms, so let’s proceed.

When we multiply using MIPS, the 64 bit result is split across 2 registers.
2147419572 * 3703353120 gives HI 1851621310, LO 888586880
2147419724 * 3703353120 gives HI 1851621441, LO 1157545344

We need to remove the bottom 48 bits. 32 of those bits are LO, the other 16 are the bottom half of HI.

Let’s look at the top and bottom 16 bits of HI.
1851621310 splits as 28253 32702, in hexadecimal 0x6e5d 0x7fbe
1851621441 splits as 28253 32833, in hexadecimal 0x6e5d 0x8041

To round up when those bottom 16 bits are 2^15 or more, we can start by adding 2^15, and then we’ll discard the bottom 16 bits.

1851621310 + 2^15 = 1851654078, splits as 28253 65470, in hexadecimal 0x6e5d 0xffbe
1851621441 + 2^15 = 1851654209, splits as 28254 00065, in hexadecimal 0x6e5e 0x0041

We have the results 28253 and 28254 that we were seeking.

8

Here is a simpler example of the same technique:

Suppose we needed to divide by 5.3333333333…

This is the same as multiplying by 0.1875

We can scale that up by 2^4: 0.1875 * 2^4 = 3

Now we can perform an integer multiplication.

As our last step, we will need to remove the bottom 4 bits from the result. Using the two registers from the MIPS multiplication result, we would conceptually have ((HI << 32) | LO) >> 4, which becomes (HI << 28) | (LO >> 4)

Adjustments can be made for rounding.

9

Thanks! That is really interesting.

10

With my new iteration, each planet uses its own scaling.