Tunguska II

eudoxie · Post by **eudoxie** » 17 Jun 2009 16:33

Figured it would be a good idea to start a separate thread for discussion of the Tunguska rewrite I'm working on.

From the big Tunguska thread: I'm seriously considering a major overhaul of the core code of Tunguska. It would be largely backwards-compatible with current Tunguska assembly code (and thus also 3CC code), but use 9 digits per word instead of 6, and add more instructions and address modes.

There are fundamental problems with Tunguska as it is right now. Most of them stem from how it was written completely ad-hoc, with no real aim or sense of direction. It is therefore poorly modularized, impossible to fork, really difficult to modify, etc. It superficially looks somewhat neat, but it really is quite a mess.

Some specifics: It will be written in C99 instead of C++, and will be much better modularized. It will be possible to take the mathematics part and use it in other code without modification (it has as few as possible assumptions hard-coded, so you can for example change the number of digits by changing a single value), and adapting the code to write other machines will be much simpler.

Since Tunguska II will use 9 digits per word, it can address much more memory (~20,000 pages x 20,000 addresses, yielding a maximum of ~400,000,000 addressable words, Tunguska I can address 500,000 words for comparison).

Therefore, memory will be allocated when it is necessary on a page-by-page basis, instead of allocating the whopping 12 Gb native memory required in one go, since almost no computer has that much memory to work with. Some sort of safeguard against a fandangoing instruction pointer will also be necessary.

Status:
* The mathematics module is mostly done, it's got some fine-tuning to be done, but it works and does what it should.
* Most instruction-code is written, but they are yet to be tested thoroughly.
* Addressing modes are implemented, but probably buggy.

Stuff to be done:
* I/O is not implemented.
* Interrupts are not implemented.
* The assembler has not been adapted to also produce Tunguska II code.

As stated previously, Tunguska II will support all Tunguska I instructions, but also add new instructions and addressing modes (a lot like Intel does when it comes up with new processors). It will not be binary compatible, but porting code should be pretty simple.

I haven't decided yet exactly what to add (suggestions are welcome), but so far I'm leaning towards a couple of new general purpose registers.

Mac Buster · Post by **Mac Buster** » 18 Jun 2009 05:42

Thanks! Good news. Any help I can provide?

hemuman · Post by **hemuman** » 18 Jun 2009 10:28

I have a question:

A lot of effort is put in preparing the Tunguska, I want to know how can it be made useful for developing applications over it?

Also is it possible to have Tundusaka II modules made/designed using XML or JSON, that way it will become cross platform, even we will be able to use it over Internet, as most of people do not download and Install the software, for them it will be an option.

All that is just suggestion.

eudoxie · Post by **eudoxie** » 18 Jun 2009 11:03

Speed is a major issue with those technologies. It's pretty important for a program like Tunguska to run fast, which typically requires host-optimized code.

It might be possible to port it to Java, though, since it can at times be pretty fast. I'll port the mathematics module of Tunguska II to Java and see how fast it runs, and if it runs fast enough, I'll consider parallel development of both a C and a Java runtime. (With java you have dynamic class loading and all sorts of fun stuff to play with)

hemuman · Post by **hemuman** » 18 Jun 2009 11:57

That sounds Great!!!

I am in, allow me to help in Java Converions and Java GUIs.

eudoxie · Post by **eudoxie** » 18 Jun 2009 12:37

I've ported the mathematics code I've written in C to Java. I haven't tested it very thoroughly, though. But superficially it seems to work for the most part. I'm gonna do some speed tests later.

Code: Select all

/* Balanced ternary arithmetics library.
 *
 * 
 *
 *
 */

package tunguska.balanced;

/**
 *
 * @author Viktor Lofgren
 * @version Test-1
 */
public class Word {

    /** Number of digits of word */
    public static final int DIGITS = 9;

    /** 3<sup>DIGITS</sup> (Maximum value of equivalent
     * non-balanced ternary form) */
    public static final int NB_MAX = 19383;

    /** Maxiumum value */
    public static final int MAX = NB_MAX/2;

    /** Minimum value */
    public static final int MIN = -MAX;

    int[] digits;

    /** Benchmark test
     *
     */
    public static void test() {


    }

    public Word() {
        digits = new int[DIGITS];
    }

    /** Performs a series of loans and carries to make sure
     * that a malformed word (e.g. [1,1,2]) is turned into a proper
     * ternary word (in this case [1, -1, -1, -1])
     *
     * @return carry
     */
    int ripple() {
          int carry = 0;
          for(int i = 0; i < DIGITS; i++) {
              digits[i] += carry;
              
              if(digits[i] > 0) {
                  carry = (digits[i] + 1) / 3;
              } else {
                  carry = (digits[i] - 1) / 3;
              }

              digits[i] -= 3*carry;
          }
          
          return carry;
    }

    int ripple1() {
        int carry = 0;
          for(int i = 0; i < DIGITS; i++) {
              digits[i] += carry;

              if(digits[i] > 0) {
                  carry = (digits[i] + 1) / 3;
              } else {
                  carry = (digits[i] - 1) / 3;
              }

              if(carry == 0) return 0;

              digits[i] -= 3*carry;
          }

          return carry;
    }

    public int[] getDigits() { return digits; }

    /** Copy the digits of a word to this word */
    public void copy(Word w) {
        for(int i = 0; i < DIGITS; i++ )
            digits[i] = w.getDigits()[i];
    }

    /** Clear all digits (effectively setting the word = 0)*/
    public void zero() {
        for(int i = 0; i < DIGITS; i++)
            digits[i] = 0;
    }

    /** Populate digit array with values equivalent to the given integer value.
     * Wrap-around if |i|>MAX
     */
    public void fromInteger(int i) {
        if(i == 0) { for(int j = 0; j < DIGITS; j++) digits[j] = 0; }
        else for(int j = 0; j < DIGITS; j++) {
            if(i < 0) {
                digits[j] = i - 3 * ((i - 1) / 3);
            } else {
                digits[j] = i - 3 * ((i + 1) / 3);
            }
            i = (i - digits[j]) / 3;
        }
    }

    /** Increment word by integer value i */
    public int addInteger(int i) {
        digits[0] += i;
        return ripple1();
    }


    /** Calculate equivalent value in host integer form */
    public final int integerValue() {
        int sum = 0;
        for(int i = DIGITS-1; i >= 0; --i) {
            sum = sum * 3 + digits[i];
        }

        return sum;
    }

    /** Return sgn(this - w) */
    public int compare(Word w) {
        int[] wDigits = w.getDigits();
        for(int i = DIGITS-1; i >= 0; --i) {
            if(digits[i] > wDigits[i]) return 1;
            else if(digits[i] < wDigits[i]) return -1;
        }
        return 0;
    }

    /** Return most significant digit */
    public int mostSignificant() {
        for(int i = DIGITS-1; i >= 0; --i) {
            if(digits[i] != 0) return digits[i];
        }

        return 0;
    }

    /** Calculate the sum of two words, put the result in a third word
     *
     * @return carry
     */
    public static int sum(Word target, Word a, Word b) {
        int carry = 0;
        int[] tdigits = target.getDigits();
        int[] adigits = a.getDigits();
        int[] bdigits = b.getDigits();
        
        for(int i = 0; i < DIGITS; i++) {
            tdigits[i] = carry + adigits[i] + bdigits[i];

            if(tdigits[i] > 0)
                carry = (tdigits[i] + 1) / 3;
            else
                carry = (tdigits[i] - 1) / 3;

            tdigits[i] -= 3*carry;
        }

        return carry;
    }

    /** Calculate the difference between two words, put the 
     * result in a third word. 
     *
     * @return carry
     */
    public static int diff(Word target, Word a, Word b) { 
        int carry = 0;
        int[] tdigits = target.getDigits();
        int[] adigits = a.getDigits();
        int[] bdigits = b.getDigits();

        for(int i = 0; i < DIGITS; i++) {
            tdigits[i] = carry + adigits[i] - bdigits[i];

            if(tdigits[i] > 0)
                carry = (tdigits[i] + 1) / 3;
            else
                carry = (tdigits[i] - 1) / 3;

            tdigits[i] -= 3*carry;
        }

        return carry;
    }

    /** Add another word onto this word 
     * @return carry
     */
    public int add(Word w) {
        int carry = 0;

        int[] wdigits = w.getDigits();

        for(int i = 0; i < DIGITS; i++) {
            digits[i] = carry + digits[i] + wdigits[i];

            if(digits[i] > 0)
                carry = (digits[i] + 1) / 3;
            else
                carry = (digits[i] - 1) / 3;

            digits[i] -= 3*carry;
        }

        return carry;
    }

   /** Subtract another word from this word 
    * @return carry
    */
    public int sub(Word w) {
        int carry = 0;

        int[] wdigits = w.getDigits();

        for(int i = 0; i < DIGITS; i++) {
            digits[i] = carry + digits[i] - wdigits[i];

            if(digits[i] > 0)
                carry = (digits[i] + 1) / 3;
            else
                carry = (digits[i] - 1) / 3;

            digits[i] -= 3*carry;
        }

        return carry;
    }

    /** Multiply two words.
     * @param target_high  High digits (may be set to null)
     * @param target_low Low digits
     * @param a  First word to be multiplied
     * @param b  Second word to be multiplied
      */
    public static void mul(Word target_high, Word target_low,
                    Word a, Word b) {
        target_low.zero();
        int[] tldigits = target_low.getDigits();
        int[] adigits = a.getDigits();
        int[] bdigits = b.getDigits();

        for(int i = 0; i < DIGITS; i++) {
            if(adigits[i] != 0) for(int j = 0; j < DIGITS - i; j++) {
                tldigits[i+j] += adigits[i] * bdigits[j];
            }
        }

        int carry = target_low.ripple();
        if(target_high != null) {
            target_high.zero();
            int[] thdigits = target_high.getDigits();

            thdigits[0] = carry;
            for(int i = 1; i < DIGITS; i++) {
                if(adigits[i] != 0) for(int j = DIGITS- i; j < DIGITS; j++) {
                    thdigits[i+j-DIGITS] += adigits[i] * bdigits[j];
                }
            }
        }

    }

    /** Divide two numbers 
     * 
     * @param remainder dividend modulo divisor (may be set to null)
     * @param quotient dividend / divisor (may be set to null)
     */
    public static void divide(Word quotient, Word remainder,
                    Word divisor, Word dividend) {
        int dr = divisor.integerValue();
        int dd = dividend.integerValue();

        /* FIXME: Deal with division by zero */
        if(dd == 0) {
            dd = 1;
        }

        if(quotient != null) quotient.fromInteger(dd/dr);
        if(remainder != null) remainder.fromInteger(dd/dr);
        
        
    };

    /** Multiply all digits by -1 */
    
    public void invert() {
        for(int i = 0; i < DIGITS; i++) {
            digits[i] *= -1;
        }
    };

    /** Shift all digits to the left */
    public void shiftLeft(int amount) { 
        int i;
        for(i = 0; i < DIGITS-amount; i++)
            digits[i] = digits[i+amount];
        
        for(; i < DIGITS; i++)
            digits[i] = 0;
        
    }

    /** Shift all digits to the right */
    public void shiftRight(int amount) {
        for(int i = 0; i < DIGITS - amount; i++)
            digits[i+amount] = digits[i];

        for(int i = 0; i < amount; i++)
            digits[i] = 0;
    };
}

hemuman · Post by **hemuman** » 18 Jun 2009 13:13

It appears that you have optimized your code alot, you have kept the complexity to "n", Great Job!!!

so this is the complete Mathematics Module ?

eudoxie · Post by **eudoxie** » 18 Jun 2009 13:43

I'm happy with the complexity of the functions, especially addInteger which has a worst-case complexity of O(n)

This is most of the module. It needs some minor fine-tuning. I'm also working on the logic code.

I did some preliminary benchmarking:

Code: Select all

        Word a = new Word();
        Word b = new Word();
        Word prod = new Word();
        for(int i = MIN; i <= MAX; i++) {
            for(int j = MIN; j <= MAX; j++) {
                a.fromInteger(i);
                b.fromInteger(j);
                Word.mul(null, prod, a, b);
            }
        }

runs in 2 minutes 37 seconds (that is pretty good, since multiplication is a very slow operation, and it's doing it 3^18 times).

Code: Select all

        word a, b, prod;
        int i, j;
        for(i = WORD_MIN; i <= WORD_MAX; i++) {
                for(i = WORD_MIN; i <= WORD_MAX; i++) {
                        bw_from_i(a, i);
                        bw_from_i(b, j);
                        bw_mul(NULL, prod, a, b)
                }
        }

Heavily optimized C code runs in (-O3): 3 minutes 45 seconds! This wasn't a very controlled experiment, but it certainly bodes well for the possibility of a full Tunguska port.

hemuman · Post by **hemuman** » 18 Jun 2009 15:13

Hi,

I am not sure of these complexities but complexity in "minutes", I think should be brought down to milliSeconds.

I had code written for addition and multiplications (for TVM),but it was just milliseconds operation for me, however it was rule based and not exactly a mathematical function.

I hope this comes down to seconds.

eudoxie · Post by **eudoxie** » 18 Jun 2009 15:23

It's running the multiplication operation 387,420,489 times for all possible values (you get a better statistical sample that way.) and that's why it takes minutes.

The time for a single loop iteration is:
0.4 microseconds for Java
0.6 microseconds for C.

The time for just the multiplication is about half that value.

This is really good. Comparing these results with calculations done with host arithmetic, it runs about 1% the speed of native mathematics (and if you consider all the "cheating" processors do with pipe lining and stuff, it's even better). It's running around the same speed as a Pentium 1.

hemuman · Post by **hemuman** » 18 Jun 2009 17:53

True, its really good and looks great!!!

I was in confusion that it takes so much time runnig the calculation, but now its Clear.

So, does Java performs better? with your algorithm, thats something unexpected.

eudoxie · Post by **eudoxie** » 18 Jun 2009 18:15

Java performance really depends a lot on the programmer. If it is written in a smart way, it can certainly out-perform C (since it's easier to optimize code that doesn't have pointers). From how I understand it, the performance loss from being an interpreted language pretty much goes away with JIT-compilation.

It is also easy to write code that is very slow in Java if you don't think about what you're doing.

Anyway, I've done some preliminary work on the architecture of Tunguska. You can have look at the javadocs to get a feel for how it's structured, if you want.

hemuman · Post by **hemuman** » 18 Jun 2009 20:26

Ya i got some picture in mind....let me know when start working on GUI for the same...i am excited to USE JavaFX for ternary.

eudoxie · Post by **eudoxie** » 19 Jun 2009 15:16

Did some major re-factoring of the code to make better use of the object orientation of Java. I've updated the javadocs (same location).

Most of the core implementation is more or less functional. I've got some preliminary benchmarks for you:

It runs 100 million instructions in 22 seconds (roughly 5 million instructions per second), same order of magnitude as an Intel 386 DX.

Tunguska does around 2 million instructions per second when you take away all the I/O, so considering that, things are looking promising

Shaos · Post by **Shaos** » 19 Jun 2009 18:51

It sounds really strange for me that Java does mathematics faster than optimized C. Do you have multicore processor or something? Did you try "vectorization" options for GCC to compile your program?

P.S. Java version is good. It means it is possible to do Android version of Tunguska-II

Tunguska II

Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II

Re: Tunguska II