基数変換のJava実装

前掲のフローチャートを素直に実装してみる。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class BaseTrans {
    private static class IncrementalList<E> extends ArrayList<E> {
        /**
         * リストの指定された位置にある要素を指定された要素で置換する。
         * 指定した位置が最後の要素の次の位置であった場合はそこに追加する。
         * @param index 置換される要素のインデックス、または、要素をリストの最後に追加する場合はsize()の値
         * @param element 指定された位置に格納される要素
         * @return 指定された位置に以前あった要素。追加した時はnull
         * @throws IndexOutOfBoundsException インデックスが範囲外(<code>index < 0 || index > size()</code>)の場合
         */
        @Override
        public E set(int index, E element) {
            if (index == size()) {
                super.add(element);
                return null;
            } else {
                return super.set(index, element);
            }
        }
    }

    public static List<BigInteger> transform(List<BigInteger> a, BigInteger A, BigInteger B) {
        IncrementalList<BigInteger> b = new IncrementalList<BigInteger>();

        int N = 1;
        b.set(0, BigInteger.ZERO);
        int m = a.size() - 1;

        do {
            BigInteger c = a.get(m);
            int n = 0;

            do {
                c = A.multiply(b.get(n)).add(c);
                b.set(n, c.mod(B));
                c = c.divide(B);
                ++n;
            } while (n < N);

            while (c.compareTo(BigInteger.ZERO) > 0) {
                b.set(n, c.mod(B));
                c = c.divide(B);
                ++n;
            }

            N = n;
            --m;
        } while (m >= 0);

        return new ArrayList<BigInteger>(b);
    }

    public static void main(String[] args) {
        class TestData {
            ArrayList<BigInteger> a = new ArrayList<BigInteger>();
            BigInteger A, B;
            List<BigInteger> b;

            /**
             * @param A 変換前の基数
             * @param B 変換後の基数
             * @param a 変換前の非負整数の各桁を最上位から最下位まで
             */
            TestData(String A, String B, String... a) {
                for (int i = a.length; --i >= 0; ) this.a.add(new BigInteger(a[i]));
                this.A = new BigInteger(A);
                this.B = new BigInteger(B);
                b = transform(this.a, this.A, this.B);
            }

            void print(List<BigInteger> x, BigInteger X) {
                BigInteger v = BigInteger.ZERO;
                for (int i = x.size(); --i >= 0; ) {
                    BigInteger xi = x.get(i);
                    v = X.multiply(v).add(xi);
                    System.out.print(xi + " ");
                }
                System.out.println("(" + X + ") = " + v + " (10)");
            }
        }

        TestData[] data = {
            new TestData("7", "3", "1", "2", "3"),
            new TestData("10", "256", "1", "2", "3", "4", "5", "6", "7"),
            new TestData("256", "10", "18", "214", "135"),
            new TestData("65536", "10", "1", "0", "0", "0"),
            new TestData("36893488147419103232", "16", "1", "0"),
            new TestData("36893488147419103232", "2", "36893488147419103231", "36893488147419103231"),
        };

        for (TestData td : data) {
            td.print(td.a, td.A);
            td.print(td.b, td.B);
            System.out.println();
        }
    }
}