Fibonacci using SBN in OISC in Machine Language

Question

I want to generate fibonacci series using SBN in an OISC architecture. My initial approach is to implement it in assembly language first and then convert it to machine language. The first steps involve storing 0 and 1 in 2 registers and then subtract 1 from 0 and repeatedly subtract 1 in the consequent steps. Everytime it will generate a negative number and since its negative, it branches off and fetches the absolute value finding instruction.

Is my approach correct? My confusion in the meaning of OISC. Correct me if i'm wrong, if i perform a subtraction and then an absolute value finding, it means that that i'm using 2 instructions everytime. or is it that in the OISC processor both these instructions are done at the sametime which would mean that my approach is correct.

Answer 1

Common assembly instructions can be synthesized from combinations of the OISC instruction. For example, taken from the Wikipedia page, addition:

ADD a, b == subleq a, Z
            subleq Z, b
            subleq Z, Z

And BEQ:

BEQ b, c == subleq b, Z, L1
            subleq Z, Z, OUT
        L1: subleq Z, Z
            subleq Z, b, c
       OUT: ...

The important insight is that once you have these building blocks, you can build more complex blocks. For instance, with ADD and BEQ you can easily implement a counting loop (which would be useful for Fibonacci...)

So you can do the following:

1. Implement Fibonacci in a normal assembly language (should take a few lines at most)
2. See what instructions you can substitute for instructions easily synthesizable from OISC instructions
3. Rewrite using OISC

Answer 2

You have 2 ways to about it:

• Your data structure contains the true (positive range) Fibonacci numbers; if so, you'd need indeed to do one calculation and one negation (what you call absolute) step, ie. minimum 2 per integer.
• Or, you could solve the 0-complement of it: -1, -1, -2, -3, -5, -8... in this way, you only simply need to negate the result to print/provide etc. That has fast 1-step calculation, but it comes at a small cost of translation when you access it (i.e. when you print it out to the user).