Ok, here is my solution in Java. BigInt makes things simple and there is no need for memoization.

    public void test25() {
        
        BigInt f1 = new BigInt(0);
        BigInt f2 = new BigInt(1);
        BigInt f3 = null;
        int i = 2;
        while(true) {
            f3 = f1.add(f2);
            f1 = f2;
            f2 = f3;
            if (f3.toString().length() >= 1000)
                break;
            i++;
        }
        res("25", 4782, i);
    }