Sample codes for implementing Large number to Text Converter and partial Big Integer module

[davidktw]

This is not a thread intended for discussion, but rather a port over of a piece of code written by me, found in the following thread found in the EDMW forum.

I believe it will stay awhile longer in this forum for interested audience to have a better understand of what I have written and how I have tackle the problem, and hopefully it will be useful to some.

The problem statement​

Can someone can translate a number from 0 to 10^20 into words

Solution​

For Big Number to Text conversion, the solution is somewhat complete, with the help of Java BigInteger class.

For Big Integer implementation portion, it's not complete and will not replace Java's BigInteger. There are a lot of things it doesn't take care of including negation, modulus, definitely no error checking, limit checking and obviously far from performant.

However it will demonstrate the concept of conversion between binary and decimal representation, boolean logic gates and why binary representation is chosen. Some of the simpler operations, such as ADDITION, can even be modelled using NAND, NOR, XOR gates which are readily available in the programming language itself.

What I am trying to achieve is to put forth a very simple statement. Knowing how to just create webpages and welding tons of programming languages or writing a few scripts is not programming and this is not even near the gold standard of Computer Science. I find often people not truly in the realm of Computer Science confused between what is a programmer and what is a script kiddie equivalent and using it as a discussion point.

If you really feel you are in the Computing way of life, the skill set requires to succeed in the computing industry is far more than just doing projects. It is a lifetime searching and passion for solving problems beyond the daily work requirement. That is a task that gives you your bread and water, but what you ought to be searching for is tasks that built your line of thoughts, your intention to use your skill to benefit people around you regardless of work or game, and last but not least your character.

It's this journey that will make you better than the sum of all parts and hence something you ought to be proud of when you go around telling people that you are a Computer Scientist. The life of a scientist is to explore and it doesn't matter if what you are exploring has already been done because in your life, it might be a totally new thing that may open up possibilities and futures that you may not have anticipated before you are even at that point.

Be a Computer Scientist, not just a programmer. However everyone is a programmer, unless you like to do manual job daily. Yet not everyone can be a Computer Scientist which many of us have pledged our life, career and hobby into part of the Computing Arena.

Hence all the best in your endeavour ahead.

Testing output

$ java NumberToText 100 401 612
B: BIN=110010001 DEC=401
C: BIN=1001100100 DEC=612
B + C: BIN=1111110101 DEC=1013
B x C: BIN=111011111010100100 DEC=245412
one HUNDRED

import java.math.BigInteger;

public class NumberToText {

  static private class BigInt {

    byte[] store = new byte[1000];

    BigInt() { }

    BigInt(String s) {
      for (int i = 0; !s.equals("0") && i < store.length; i++) {
        Object[] r = divBy2(s);
        store[i]   = ((Integer)r[1]).byteValue();
        s = (String)r[0];
      }
    }

    BigInt(BigInt i) {
      System.arraycopy(i.store, 0, store, 0, i.store.length);
    }

    BigInt shiftLeft(int i) {
      BigInt d = new BigInt();
      System.arraycopy(store, 0, d.store, i, store.length - i);
      return d;
    }

    BigInt shiftRight(int i) {
      BigInt d = new BigInt();
      System.arraycopy(store, i, d.store, 0, store.length - i);
      return d;
    }

    BigInt multiply(BigInt b) {
      BigInt d = new BigInt();

      for (int i = 0; i < b.store.length; i++) {
        BigInt e = new BigInt(this).shiftLeft(i);
        for (int j = 0; j < e.store.length; j++)
          e.store[j] &= b.store[i];
        d = d.add(e);
      }

      return d;
    }

    BigInt add(BigInt b) {
      BigInt d = new BigInt();
      int over = 0;
      for (int i = 0; i < store.length; i++) {
        d.store[i] = (byte)(store[i] ^ b.store[i] ^ over);
        over = (byte)(((store[i] ^ b.store[i]) & over) |
                      (store[i] & b.store[i]));
      }
      return d;
    }

    private static Object[] divBy2(String s) {
      StringBuilder t = new StringBuilder(s.length());
      int m = 0;
      int r = 0;
      for (int i = 0; i < s.length(); i++) {
        m = m * 10 + s.charAt(i) - '0';
        if (m >= 2)
          t.append(m >> 1);
        else
          t.append('0');
        if (t.charAt(0) == '0')
          t.deleteCharAt(0);
        r = m % 2;
        m -= m >> 1 << 1;
      }
      return new Object[] { t.toString(), new Integer(r) };
    }

    private static StringBuilder mulBy2(StringBuilder s) {
      StringBuilder t = new StringBuilder(s);
      int over = 0;
      for (int i = s.length() - 1; i >= 0; i--) {
        int val = (s.charAt(i) - '0') * 2 + over;
        over = val / 10;
        t.setCharAt(i, (char)('0' + val % 10));
      }
      if (over > 0)
        t.insert(0, (char)('0' + over));
      return t;
    }

    private static StringBuilder addBit(StringBuilder s, int b) {
      StringBuilder t = new StringBuilder(s);
      int over = b;
      for (int i = s.length() - 1; i >= 0; i--) {
        int val = s.charAt(i) - '0' + over;
        over = val / 10;
        t.setCharAt(i, (char)('0' + (val % 10)));
      }
      if (over > 0)
        t.insert(0, (char)('0' + over));
      return t;
    }

    String getDecStr() {
      StringBuilder t = new StringBuilder(store.length);

      t.append("0");
      for (int i = store.length - 1; i >= 0; i--) {
        t = addBit(mulBy2(t), store[i]);
      }
      return t.toString();
    }

    String getBinStr() {
      StringBuilder t = new StringBuilder(store.length);
      boolean lead = true;
      for (int i = store.length - 1; i >= 0; i--) {
        lead &= store[i] == 0;
        if (!lead)
          t.append(store[i]);
      }
      if (lead) t.append("0");
      return t.toString();
    }
  }

  private static String[] _1To19 = new String[] {
    "zero", "one", "two", "three", "four", "five", "six",
    "seven", "eight", "nine", "ten", "eleven", "twelve",
    "thirteen", "fourteen", "fifteen", "sixteen", "seventeen",
    "eighteen", "nineteen"
  };
  private static String[] _20To90 = new String[] {
    "zero", "ten", "twenty", "thirty", "forty",
    "fifty", "sixty", "seventy", "eighty", "ninety"
  };
  private static String[] _UNITS = new String[] {
    "VIGINTILLION", "NOVEMDECILLION", "OCTODECILLION", "SEPTENDECILLION",
    "SEXDECILLION", "QUINDECILLION", "QUATTUORDECILLION", "TREDECILLION",
    "DUODECILLION", "UNDECILLION", "DECILLION", "NONILLION", "OCTILLION",
    "SEPTILLION", "SEXTILLION", "QUINTILLION", "QUADRILLION", "TRILLION",
    "BILLION", "MILLION", "THOUSAND"
  };

  private static final BigInteger _ZERO         = BigInteger.ZERO;
  private static final BigInteger _TEN          = BigInteger.TEN;
  private static final BigInteger _TWENTY       = new BigInteger("20");
  private static final BigInteger _HUNDRED      = new BigInteger("100");
  private static final BigInteger _THOUSAND     = new BigInteger("1000");
  private static final BigInteger _VIGINTILLION = _TEN.pow(63);

  public static void main(String[] args) {
    BigInt b = new BigInt(args[1]);
    BigInt c = new BigInt(args[2]);

    System.out.println("B: BIN=" + b.getBinStr() + " DEC=" + b.getDecStr());
    System.out.println("C: BIN=" + c.getBinStr() + " DEC=" + c.getDecStr());
    BigInt x = b.add(c);
    BigInt y = b.multiply(c);
    System.out.println("B + C: BIN=" + x.getBinStr() + " DEC=" + x.getDecStr());
    System.out.println("B x C: BIN=" + y.getBinStr() + " DEC=" + y.getDecStr());

    System.out.println(getText(args[0]));
  }

  static String getText(String s) {
    s = getText(new BigInteger(s)).trim().replaceAll("\\s+", " ");
    if (s.endsWith("zero") && s.length() > 4)
      s = s.substring(0, s.length() - 4);
    return s;
  }

  static String getText(BigInteger i) {

    if (i.compareTo(_ZERO) < 0)
      return "negative " + getText(i.negate());
    if (i.compareTo(_ZERO) == 0)
      return "zero";

    BigInteger d = _VIGINTILLION;
    for (int j = 0; j < _UNITS.length; j++) {
      if (i.compareTo(d) >= 0)
        return getText(i.divide(d)) + " " + _UNITS[j] + " " + getText(i.mod(d));
      d = d.divide(_THOUSAND);
    }

    if (i.compareTo(_HUNDRED) >= 0)
      return getText(i.divide(_HUNDRED)) + " HUNDRED " + getText(i.mod(_HUNDRED));

    if (i.compareTo(_TWENTY) < 0)
      return _1To19[i.intValue()] + " ";
    if (i.compareTo(_HUNDRED) < 0)
      return _20To90[i.intValue() / 10] + " " + getText(i.mod(_TEN));

    return "";
  }
}

 

[watchy]

What practical use can we extract from your described problem?

 

[davidktw]

What practical use can we extract from your described problem?

What is considered practical use to you ? Would you consider learning how to implement a low level adder be of practical use to you ?