Similarities and differences between Java and C

As almost everybody knows Java was intended to be sort of C without pointers and to be used in smart home appliances. And then Gosling and his co-workers were drinking too much coffee and it come out more like C++ without pointers, resource management and multiple inheritance. So, how really different can be coding the same task in C and Java. Practically we are addressing just resource management part, we will not try to go OO in C. We implement fast Fibonacci algorithm in Java.

import java.math.BigInteger; public class Example { /* |1 1| <- we are using this row |1 0| */ static BigInteger[] Q = {BigInteger.ONE, BigInteger.ONE}; static BigInteger[] I = {BigInteger.ONE, BigInteger.ZERO}; /* F(2n+1) = F(n+1)^2+F(n)^2 F(2n) = F(n)*(2*F(n+1)−F(n)) */ static BigInteger[] squareIt(int n) { if (n == 0) return I; if (n == 1) return Q; BigInteger[] t = squareIt(n / 2); BigInteger[] res = {t[0].multiply(t[0]).add(t[1].multiply(t[1])), t[1].multiply(t[0].shiftLeft(1).subtract(t[1]))}; if(n%2==1) return new BigInteger[]{res[0].add(res[1]), res[0]}; return res; } public static void main(String[] env) { for(int i = 0; i<1000; i++) System.out.println("F("+i+") = "+squareIt(i)[1]); } }

It is really very fast, logarithmic fast. Now we try to do the same in C, we will skip BigInteger and use long. The first thing which wont work in C is array allocation, declaring them like that will create local variable. So we create function to allocate our arrays in order to return them to caller:

long * allocate(){ return (long*)malloc(2 * sizeof(long)); }

Those Q and I arrays can be global variables and we are ready to go, almost. We can not declare t as array since initializer can't be function call. Not big deal, we will use pointer to long but that introduces another problem. That pointer may point to global variables Q and I or allocated variables. Again we can check to what it points and if it doesn't point to Q or I we can call free. Already we have feeling that those arrays returned by squaring function are somehow polymorphic and in Java they were not like that. Allocating and freeing arrays on every step of recursion and checking should we free or not doesn't look right. Attempt to literally translate Java code may look something like this:

long * recurse(int i){ if(i==0) return I; if(i==1) return Q; long * t = recurse(i/2); long * r = allocate(); r[0] = t[0]*t[0]+t[1]*t[1]; r[1] = t[1]*((t[0]<<1)-t[1]); checknfree(t); if(i%2){ long * odd = allocate(); odd[0] = r[0]+r[1]; odd[1] = r[0]; free(r); return odd; } return r; }

If Q and I arrays are created using malloc we could do reassignments of initial array and free it at the end of calculation. So no global Q and I but they will be allocated on the heap and serve all recursive calls.

#include <stdio.h> #include <stdlib.h> long * allocate(int i){ long* res = (long*)malloc(2 * sizeof(long)); res[0] = 1; res[1] = i; return res; } long * recurse(int i){ if(i<2) return allocate(i); long * t = recurse(i/2); long t0 = t[0]*t[0]+t[1]*t[1]; t[1] = t[1]*((t[0]<<1)-t[1]); t[0] = t0; if(i%2){ t0 = t[0]+t[1]; t[1] = t[0]; t[0] = t0; } return t; } long square(int n){ long * result = recurse(n); long r = result[1]; free(result); return r; } int main(){ int i; for(i=0; i<93; i++) printf("F(%d) = %ld\n", i, square(i)); return 0; }

Now if we run valgrind on our program it will report:

==18896== HEAP SUMMARY:
==18896==     in use at exit: 0 bytes in 0 blocks
==18896==   total heap usage: 93 allocs, 93 frees, 1,488 bytes allocated
==18896== 
==18896== All heap blocks were freed -- no leaks are possible

Looking now at initial Java solution, it also could benefit from array reuse instead of allocating new ones on every step. Garbage collector is nice thing but not thinking at all about resource management may result in lower quality of code.