Little programming challenge: Factorials

[timo]

Since people asked what happened to the SFN Brain Challenges and since the number of participants in YT's "build something"-challenges is approximately zero I've thought that a litte JAVA programming exercise might suit the SFN members better. So here we go with a little programming challenge.

 

GOAL:

- Create a program that calculates factorials.

 

TARGET AUDIENCE:

- Anyone with zero programming experience to experienced programmers.

- For complete beginners, I'll post some startup tips so you should at least be able to get a program with limited capabilities running quite easily.

 

RULES:

- Challenge will run approximately 4 weeks.

- The structure of the main program is already given, so don't worry about it.

- Only edit the file Math.java.

- No includes may be used, i.e, no "import ..." may appear in the code.

- No precomputed lookup-tables (btw, we have a new smiley)

- The text returned must contain the complete result as a plain number i.e. no shortcuts like 124E10.

 

EVALUATION CRITERIA:

- Working code: The values returned should be the correct ones.

- Clean code: Others should be able to read and understand the code, too. This criterion includes clear program structure, usage of understandable algorithms and proper commenting.

- Resource saving and flexibility: The biggest number that can sensibly be calculated and the system resources used/needed.

- Performance: The faster the better.

 

GENERAL INFORMATION:

- A clean Netbeans project is appended to this post. When you are finished, send me the Math.java file (the one you should edit) via PM. You are of course not forced to use the provided interface but I will paste your Math.java file in a similar one for testing, so make it compatible.

- There is a simple tool for performace-checks from one of my other programs that I included to the code. Use it or leave it be; usage should be pretty simple/straightforward.

- For completely clueless people, I have set up a mini-introduction at WiSci: http://www.wisci.org/wiki/User:Timo/FactorialIntro#Factorial_Guide_for_Dummies. It's a wiki so corrections and improvements by someone else are welcome, but keep in mind that it's only supposed to be a minimal starter.

- If you're stuck, or want feedback on your current state (working version only, pls), then post here. Especially in the case of complete beginners wanting to participate, I'd like to have some intermediate feedback - there's a few not-so-completely-trivial issues involved that I (or others) might reveal over time (as soon as you've hit the wall yourself ).

SFNFactorial.zip

[bascule]

Erlang:

 

-module(factorial).
-export([calc/1]).

calc(0) -> 1;
calc(X) -> X * calc(X - 1).

 

Uhoh, I think I broke the rules

[Rocket Man]

fact is the input variable

out is the output variable

 

out =1

for a = 1 to fact
out = a*out
next a

sorry about the shitty syntax, i use VB

[timo]

Given the lack of reaction in here, two non-valid (no conversion from and to string, not the Math.java file given) contributions and the comments here I think it might be time to give out the first hint: Up to what number n do you expect these two pseudo-codes to be able to calculate n! ?

 

Also, pls refrain from posting pseudo-code or code not compatible with the challenge rules. Code being compatible with the rules will be considered an entry to the challenge.

[Rocket Man]

it may help if you opened it to all forms of coding. i for one can put a lot into vb but i've never heard of math.java

 

my code is all vb which is arguably a pseudo code. if i wanted to write a program that needed factorials, that would be the exact code i'd use word for word.

that algorythm is limited by the type of variable the output set up as.

if i said:

dim out as currency

it would allow me to calculate up to 922,337,203,685,447.

which isn't much in terms of factorials. i'm pretty sure it's anything under 18!

[timo]

it may help if you opened it to all forms of coding. i for one can put a lot into vb but i've never heard of math.java

- math.java is just the name I gave to the file. It's a pretty empty class except for returning the string "your code comes here" when the method factorial(string s) is called.

- I have several reasons why the language is given. Apart from taking spoiler languages like Mathematica that already implement factorials or a large proportion of the code needed, I don't see where any language should offer much over Java. For me, object-oriented languages are all pretty much the same with the differences lying in details that are not relevant here (you will most likely not need operator overloading, you will most likely not need multiple inheritances, ...).

- As long as the codes do not become too complex, I do in general not have a problem to port them to Java, myself. But that opens up the question why I should do the porting and not the coder himself. You could ask around for someone more proficient (or interested) in Java who could do that.

- In Java, your code would read

int out=1;
for (int a=1; a<=fact; a=a+1) out = out*a;

In other word: Most (if not all) of the control structures you know from VB exist in Java, too. They only have slightly different notations which shouldn't be too hard to figure out (google for java for loop to find out the structure of the loop, for example).

 

it [the VB code] would allow me to calculate up to 922,337,203,685,447.

which isn't much in terms of factorials. i'm pretty sure it's anything under 18!

Yes, 17! would be your limit.

[bascule]

Yes, 17! would be your limit.

 

Which shows the folly of relying on CPU primitives for number handling. You run into arbitrary limitations.

 

I was able to calculate the factorial of 30000 in approximately 12 seconds (benchmarked!) with the above Erlang code (on a 2GHz Core 2 Duo). The number it output was so large it exceeded the scrollback of my terminal.

[timo]

You've almost found out what the whole challenge is about. Hint: It's not about your love for some programming language.

[bascule]

You've almost found out what the whole challenge is about. Hint: It's not about your love for some programming language.

 

So it's about how painfully limiting Java is?

[Aeternus]

http://pastie.caboo.se/68663

 

I haven't finished it yet but it does the basics (does around 5000! within a few seconds for me). I'll tidy it up and fix it up tonight so it can use int[] instead and a much larger base so as to reduce multiplications (I need to write the base conversion bits first, I have started but not finished yet) and there's a few other things that should help it. The limit of 200000 digits is arbitrary as I couldn't be arsed to expand the array etc every so often but it's easy enough to do or to use a formula to work out the number of digits.

[timo]

Looks very nice. I've implemented and tested it. Seems to work fine so far. I plan to test the different codes against each other by running them from a common main prog similar to the one attached in the zip-file above. To automatically test the various codes against each other, that requires that the code actually returns a string rather than printing it to the console and also that the leading zeros of your result are cleaned up (I could do that in the main code, too - but it's an ugly-looking result, anyways).

[Aeternus]

Yeah, it was just hacked together so there are a few issues with the leading zeroes etc. I'll tidy it up in the next few days and post a nicer version. The idea is simple enough, it just does long multiplication on base N numbers stored in an array, atm it uses 10 as the base for simplicity. Sadly, it'll get slower as time goes on as long multiplication between longer numbers requires more operations, but I guess that's the case with most arbitrary precision number classes (although I imagine most precision number classes have a lot more operations and are a lot more sophisticated )

[Aeternus]

class Math {


   public static String factorial( String value ) {
       BigNatural a = new BigNatural("1");   
       BigNatural b = new BigNatural(value);
       int val = Integer.parseInt(value);
       while(val >= 2) {
           a.multiply(b);
           b.decrement();
           val--;
       }
       return a.toString();
   }

   public static void main ( String args[] ) {
       System.out.println(factorial(args[0]));
   }

   static public class BigNatural {
       // We store the values as a base255 number (we use 255 to represent the end of the list for speed of calculation)
       public int base = 10;
       public static final int DEFAULT_BASE = 2000000;
       public static final int MAX_LENGTH = 200000;
       private int[] value;
       // Used for intermediate calculations and we don't
       // want them remade every time as that would be rather
       // slow.
       private int[] finalResult;

       public BigNatural(String strVal) {
           this(strVal,DEFAULT_BASE);
       }

       public BigNatural (String strVal, int base) {
           //int val = Integer.parseInt(strVal); // Clearly we won't be able to compute more than the range of int factorial
           value = new int[MAX_LENGTH];
           this.base = base;
           finalResult = new int[MAX_LENGTH];
           // Init
           value[0] = 0;
           finalResult[0] = 0;
           finalResult[1] = -1;
           // Set value
           set(strVal);
       }

       /** 
        * Decrements by 1
        */
       public void decrement() {
           long intVal = value[0]; // No unsigned bytes :'(
           int i = 0;
           while (intVal == 0) {
               intVal = value[++i];
           }
           value[i--]--;
           while(i >= 0){ value[i] = (base - 1); i--; }
           //value[0] = (byte) intVal;
       }

       /**
        * Sets the current number to a new number
        */
       public void set( String strVal ) {
           // Set value
           set(Integer.parseInt(strVal));
       }

       public void set(long val) {
           int i = 0, j = 0;
           long pow = 1;
           while ((val / pow) >= 1) { pow *= base; i++; }
           j = i;
           while(i >= 0) {
               value[i--] = (int)(val / pow);
               val = val % pow;
               pow /= base;
           }
           value[j] = -1;
       }

       /**
        * Converts to a denary string
        */
       public String toString() {
           BigNatural power = new BigNatural(new String("" + base),1000000); 
           //BigNatural powerRaiser = new BigNatural(new String("" + base),(byte)10);
           BigNatural tmpValue = new BigNatural("0",1000000);
           BigNatural powerUp = new BigNatural("1", 1000000);
           BigNatural newValue = new BigNatural("0", 1000000);
           // Iterate over digits
           int i = 0;
           while((value[i] >= 0)) {
               tmpValue.set(value[i]);
               tmpValue.multiply(powerUp);
               newValue.add(tmpValue);
               powerUp.multiply(power);
               i++;
           }
           int[] bytes = newValue.getBytes();
           i = 0;
           while(bytes[i++] >=0); i--; i--;
           StringBuilder x = new StringBuilder(i);
           if (i >= 0) x.append(bytes[i--]);
           while(i>=0) {
               x.append(padWithZeroes(bytes[i--],6));
           }
           return x.toString();
       }

       public static String padWithZeroes(int x, int len) {
           String xs = new String("" + x);
           StringBuilder g = new StringBuilder();
           for(int i = xs.length(); i < len; i++) {
               g.append('0');
           }
           g.append(xs);
           return g.toString();
       }


       public void printString() {
           int i = 0;
           while(value[i++] >= 0); i--;i--;
           while(i >= 0) {
               System.out.print(value[i--]);
           }
           System.out.println();
       }

       /**
        * Multiplies this big number with the other and stores the value in this 
        * one .
        *
        * This stores the result in this object sine I wish to avoid creating 
        * lots of objects over and over as this will be horribly inefficient 
        * and garbage collection will probably not be able to keep up.
        * 
        * This basically does long multiplication in base
        */
       public void multiply(BigNatural other) {
           int[] otherBytes = other.getBytes();
           int i = 0;
           int j = 0;
           long intVal = 0;
           long overflow = 0;
           finalResult[0] = 0 ;
           finalResult[1] = -1;

           // Iterate over a's digits
           while(value[i] >= 0) {
               // Multiply by every b digit
               j = 0;
               overflow = 0;
               while(otherBytes[j] >= 0) {
                   if (finalResult[j+i] < 0) { finalResult[j+i] = 0; finalResult[j+i+1] = -1; }
                   intVal = (long)finalResult[j+i] + ((long)value[i] * (long)otherBytes[j]) + overflow;
                   overflow = intVal / base;
                   intVal = intVal % base;
                   finalResult[j+i] = (int)intVal;
                   j++;
               }
               while (overflow > 0) {
                   if (finalResult[j+i] < 0) { finalResult[j+i] = 0; finalResult[j+i+1] = -1; }

                   intVal = finalResult[j+i] + overflow;
                   overflow = intVal / base;
                   intVal = intVal % base;
                   finalResult[j+i] = (int)intVal;
                   j++;
               }
               value[i] = finalResult[i];
               i++;
           }
           // Put back in value
           while (finalResult[i] >= 0) {
               value[i] = finalResult[i++];
           }
           value[i] = -1;
       }


       private int[] getBytes() {
           return value;
       }

       /**
        * Adds two raw big naturals together
        */
       public void add(BigNatural bigB) {
           int[] a = value;
           int[] b = bigB.getBytes();
           long overflow = 0;
           long intVal = 0;
           int i = 0;
           while((b[i] >= 0)) {
               if (a[i] < 0) { a[i] = 0; a[i+1] = -1; }
               intVal = a[i] + b[i] + overflow;
               overflow = intVal / base ;
               intVal = intVal % base;
               a[i] = (int)intVal;
               i++;
           }
           while(overflow > 0) {
               if (a[i] < 0) { a[i] = 0; a[i+1] = -1; }
               if (b[i] < 0) { b[i] = 0;b[i+1] = -1; }
               intVal = a[i] + b[i] + overflow;
               overflow = intVal / base ;
               intVal = intVal % base;
               a[i] = (int)intVal;
               i++;
           }
       }
   }
}

 

There's the new revised edition. I may get around to commenting it and tidying things up a bit more, depending on whether I can be bothered etc.

 

It isn't as fast as using other precision number classes but it works well enough. The conversion from base 2 billion to 10 is a bit iffy, it is a lot faster now I realised that you can convert to base 1 billion and pad digits with 0s.

 

It does 10000! on my macbook (1.83Ghz Core Duo) in around 14-15s but takes around 1 minutes and a bit to calculate 20000! so you can see that the complexity isn't nice and it won't be winning any awards any time soon

 

On my desktop (2.4Ghz Core 2 Duo) it manages 20000! in 27s and 30000! in about the same time as the my macbook handles 20000! which is better still I don't think it'll be beating Erlang any time soon, heh.

[Aeternus]

class Math {

  private static final long NON_BIGNUM_LIMIT = (long)2000000000 * (long)2000000000;

   public static String factorial( String value ) {
       BigNatural a = new BigNatural("1");   
       BigNatural b = new BigNatural(value);
       int val = Integer.parseInt(value);
       long currentValue = 1;
       while(val >= 2) {
           while (((NON_BIGNUM_LIMIT / currentValue) > val) && (val >= 2)) {
               currentValue *= val--;
           }
           b.set(currentValue);
           a.multiply(b);
           currentValue = 1;
           //b.decrement();
           //val--;
       }
       return a.toString();
   }

   public static void main ( String args[] ) {
       System.out.println(factorial(args[0]));
   }

   static public class BigNatural {
       // We store the values as a base255 number (we use 255 to represent the end of the list for speed of calculation)
       public int base = 10;
       public static final int DEFAULT_BASE = 2000000000;
       public static final int MAX_LENGTH = 200000;
       private int[] value;
       // Used for intermediate calculations and we don't
       // want them remade every time as that would be rather
       // slow.
       private int[] finalResult;

       public BigNatural(String strVal) {
           this(strVal,DEFAULT_BASE);
       }

       public BigNatural (String strVal, int base) {
           //int val = Integer.parseInt(strVal); // Clearly we won't be able to compute more than the range of int factorial
           value = new int[MAX_LENGTH];
           this.base = base;
           finalResult = new int[MAX_LENGTH];
           // Init
           value[0] = 0;
           finalResult[0] = 0;
           finalResult[1] = -1;
           // Set value
           set(strVal);
       }

       /** 
        * Decrements by 1
        */
       public void decrement() {
           long intVal = value[0]; // No unsigned bytes :'(
           int i = 0;
           while (intVal == 0) {
               intVal = value[++i];
           }
           value[i--]--;
           while(i >= 0){ value[i] = (base - 1); i--; }
           //value[0] = (byte) intVal;
       }

       /**
        * Sets the current number to a new number
        */
       public void set( String strVal ) {
           // Set value
           set(Long.parseLong(strVal));
       }

       public void set(long val) {
           int i = 0, j = 0;
           long pow = 1;
           while ((val / pow) >= 1) { pow *= base; i++; }
           //System.out.println("Power " + pow + " val " + val);
           j = i;
           while(i >= 0) {
               value[i--] = (int)(val / pow);
               val = val % pow;
               pow /= base;
           }
           value[j] = -1;
       }

       /**
        * Converts to a denary string
        */
       public String toString() {
           BigNatural power = new BigNatural(new String("" + base),1000000); 
           //BigNatural powerRaiser = new BigNatural(new String("" + base),(byte)10);
           BigNatural tmpValue = new BigNatural("0",1000000);
           BigNatural powerUp = new BigNatural("1", 1000000);
           BigNatural newValue = new BigNatural("0", 1000000);
           // Iterate over digits
           int i = 0;
           while((value[i] >= 0)) {
               tmpValue.set(value[i]);
               tmpValue.multiply(powerUp);
               newValue.add(tmpValue);
               powerUp.multiply(power);
               i++;
           }
           int[] bytes = newValue.getBytes();
           i = 0;
           while(bytes[i++] >=0); i--; i--;
           StringBuilder x = new StringBuilder(i);
           if (i >= 0) x.append(bytes[i--]);
           while(i>=0) {
               x.append(padWithZeroes(bytes[i--],6));
           }
           return x.toString();
       }

       public static String padWithZeroes(int x, int len) {
           String xs = new String("" + x);
           StringBuilder g = new StringBuilder();
           for(int i = xs.length(); i < len; i++) {
               g.append('0');
           }
           g.append(xs);
           return g.toString();
       }


       public void printString() {
           int i = 0;
           while(value[i++] >= 0); i--;i--;
           while(i >= 0) {
               System.out.print(value[i--]);
           }
           System.out.println();
       }

       /**
        * Multiplies this big number with the other and stores the value in this 
        * one .
        *
        * This stores the result in this object sine I wish to avoid creating 
        * lots of objects over and over as this will be horribly inefficient 
        * and garbage collection will probably not be able to keep up.
        * 
        * This basically does long multiplication in base
        */
       public void multiply(BigNatural other) {
           int[] otherBytes = other.getBytes();
           int i = 0;
           int j = 0;
           long intVal = 0;
           long overflow = 0;
           finalResult[0] = 0 ;
           finalResult[1] = -1;

           // Iterate over a's digits
           while(value[i] >= 0) {
               // Multiply by every b digit
               j = 0;
               overflow = 0;
               while(otherBytes[j] >= 0) {
                   if (finalResult[j+i] < 0) { finalResult[j+i] = 0; finalResult[j+i+1] = -1; }
                   intVal = (long)finalResult[j+i] + ((long)value[i] * (long)otherBytes[j]) + overflow;
                   overflow = intVal / base;
                   intVal = intVal % base;
                   finalResult[j+i] = (int)intVal;
                   j++;
               }
               while (overflow > 0) {
                   if (finalResult[j+i] < 0) { finalResult[j+i] = 0; finalResult[j+i+1] = -1; }

                   intVal = finalResult[j+i] + overflow;
                   overflow = intVal / base;
                   intVal = intVal % base;
                   finalResult[j+i] = (int)intVal;
                   j++;
               }
               value[i] = finalResult[i];
               i++;
           }
           // Put back in value
           while (finalResult[i] >= 0) {
               value[i] = finalResult[i++];
           }
           value[i] = -1;
       }


       private int[] getBytes() {
           return value;
       }

       /**
        * Adds two raw big naturals together
        */
       public void add(BigNatural bigB) {
           int[] a = value;
           int[] b = bigB.getBytes();
           long overflow = 0;
           long intVal = 0;
           int i = 0;
           while((b[i] >= 0)) {
               if (a[i] < 0) { a[i] = 0; a[i+1] = -1; }
               intVal = a[i] + b[i] + overflow;
               overflow = intVal / base ;
               intVal = intVal % base;
               a[i] = (int)intVal;
               i++;
           }
           while(overflow > 0) {
               if (a[i] < 0) { a[i] = 0; a[i+1] = -1; }
               if (b[i] < 0) { b[i] = 0;b[i+1] = -1; }
               intVal = a[i] + b[i] + overflow;
               overflow = intVal / base ;
               intVal = intVal % base;
               a[i] = (int)intVal;
               i++;
           }
       }
   }
}

 

Slight improvement, that avoids using the BigNatural class as much as possible. Doesn't really make a huge difference by tends to knock off around about 20% of the time.

 

[Edit]

Didn't realise, it should have been using base 2 billion, not 2 million That sped things up a little bit.

[timo]

WEEK 1+ FEEDBACK AND ADDITIONAL INFORMATION

--------------------------------------------------

 

Lost my text due to hitting the page-back button on my mouse . So let's make it short:

 

- The problem stands as is, which particularly includes the restrictions to use Java and not to include the BigNumber class. Pls don't post solutions to different problems - I do know that you can get 100000! very quickly with a single line in Mathematica.

 

- For the basic algorithm to calculate n!, two different styles of solution have been presented. A recursive approach by Bascule and an iterative solution by RocketMan. Both have their own strength and weaknesses: Recursions tend to be more stylish and read more clearly while iterations tend to be faster and less ressource-intensive. It's your choice what you prefer and why.

 

- The basic data structures you are allowed to use only allow calculations up to about 20!. To get the factorial of bigger numbers, you have to write your own structures which support bigger numbers. This is in fact the main objective in this challenge. There's different ways to do so:

* You could try operating on the strings directly, starting with "1" and then consecutively multiplying the string by increasing numbers.

* You can write your own class supporting big integers. These will probably store the number as digits in a base B. The possible choices of B that come to mind first are either 10^n (which makes conversions to the resulting string relatively easy) or 2^n (which is similar to the base internally used by the computer and therefore seems to be the fastest choice). Aeternus has taken a very interesting choice which basically is a 10^n one, but with a factor of 2 that can be converted to a factor of 1 relatively easy and also slightly decreases the number of digits needed (therefore decreasing the number of steps the computer must make to multiply the number). I do not recommend starting with a base that you don't know how to convert to base 10 afterwards, or at least write the translation to a string first. For storing the different digits of the chosen base, I see two main options. Either use an array like Aeternus or use a linked list. Parsing the different digits (for conversion or the mathematical operations) again can either be done recursively or iteratively with again both methods having the same advantages and disadvatages (although they might weight differently, here).

 

- Since a class for arbitrarily big integers already exist in Java, reusability of the code (for example for YT to get really, really large primes) should not be a major concern. It will add to the "flexibility" criterion of the evaluation criteria but realistically, you're not likely to ever use your structure again (unless you find a really great solution, of course).

[timo]

@Aeternus: I've only glanced at your code so far. Since this is a programming challenge and not a group programming project (I've thought about making it a group project but then realized to success of past sfn-inspired projects and skipped the idea) I don't want to give out too much information too early. Also, nothing guarantees that my ideas are better than those of others, so I'd also risk shutting down potentially good ideas. So here's just two small remarks on your code:

- You can trick the integers of Java into unsigned ones by "long l = ( i & 0xffffffffL)". You might be able to go to base 4*10^9 that way.

- What is the biggest factorial you realistically expect being able to calculate? Could that result in some optimization of your code, particlarly the multiplication ?

[Aeternus]

Just realised, I forgot to change padWithZeroes to pad it out to 9 digits when I changed to base 2 billion. I'll add a new fixed version soon with some more comments. Changing down to base 1 billion and just padding the digits is far quicker as my original base conversion was a bit slow.

 

Atheist, while I understand what you are saying and am aware of the fact that you can hack around the lack of signed integers (I used the same hack in my original code with bytes and I also had to do this when doing image manipulation stuff for one of my graphics modules), I think 4*10^9 would be too large as during the multiplication I will have to store the result of the multiplication of 2 digits , which I won't be able to store in a *signed* long with that large a number (ie potentially (4*10^9 - 1) * (4 * 10^9 -1) = ~16 * 10^18 whereas the max long is ~9 * 10^18). That along with the fact that conversion to a string at the end is easier with base 1 * 10^9 makes me think that uping to something like base 3 * 10 ^ 9 which might fit, would be less rewarding.

 

I'm looking into speeding it up in other ways and am keeping your comments in mind

 

[edit]

http://pastie.caboo.se/69641

 

Here is the new code. It is rather a bit faster than the previous but I can still think of a few potential improvements (as I'm sure you are suggesting there are). It now manages 30000! in 6s on my desktop and 50000! in 20s. I'll try making it a little more robust in a little while by having an increasing size array (which will double or similar in size when it reaches it's make to avoid too many problems), which may slow it down a bit but might open the doors for a more interesting approach than a for loop, as well as reducing problems as given that it now calculates much larger numbers in a much smaller time, the increasing small arbitrary limit of 200000 digits (although in base 10^9) could become problematic (especially as it isn't error checked at present).

[Aeternus]

http://pastie.caboo.se/70939

 

New Version which grows the array when needed and does the calculation in a more tree like fashion to improve the speed a little (so you are more often multiplying small numbers than big which are easier to compute with).

[Aeternus]

https://aeternus.no-ip.org/factorial-trac/trac.cgi/browser/Math.java?rev=20

 

Some improvements and some changes that may be for the worse in terms of range. I looked at the multiplication and decided to use the Karatsuba method of multiplication to speed things up a bit. This is fairly simple compared to some of the multiplication algorithms (such as Schonhage-Strassen) but most of the others seemed to be FFT algorithms which I don't know enough about to begin implementing them.

 

This doubled the speed (to the effect that it now calculates 1000000! in around 1 hour 20 minutes instead of 2 hours 40) but means that, given my implementation, it takes quite a lot of memory compared to the previous implementation (just over 1GB was used when calculating 1000000!). I'm not sure how much of this was garbage collection issues etc but I imagine that a lot of it was my poor implementation of things.

 

I plan eventually to look into improving this some more (especially with the neatness and overall correctness), perhaps by looking at the other algorithms but I have a lot of reading to do before that and I'll probably implement some kind of JUnit tests or try to prove the correctness of some of the building block operations.

[timo]

I can't take the code from your page (I can, but then I have the nasty numbers when I copy/paste) and haven't looked into it, yet. One thing which you probably didn't pay attention to: Multiplication by factors of 10 is really easy in decimal base!

[Aeternus]

I can't take the code from your page (I can, but then I have the nasty numbers when I copy/paste) and haven't looked into it, yet. One thing which you probably didn't pay attention to: Multiplication by factors of 10 is really easy in decimal base!

 

You can just click plain text at the bottom or https://aeternus.no-ip.org/factorial-trac/trac.cgi/browser/Math.java?rev=20&format=txt .

 

You are correct, I didn't think of that Sorry it's a little messy at the moment (comments etc all over) but I haven't had a chance to remove them.

[timo]

Well, the ~4 weeks are over. There's only one entry so comparison of the codes and discussion of the different approaches is skipped.

@Aeternus: You can check your results and compare with the primitive BigInteger version yourself, so I'll skip that, too (I assume you did check your results, anyways). If you want to, I can have a look at your code and give some comments, but I'm not sure that there's much to get out of it for you.

[Aeternus]

Well it was a fun challenge I will almost certainly come back to the stuff I have at some point to make improvements, I just need to do more reading up on certain areas to approach some of the more elaborate algorithms I want to use. I recently got my project/dissertation topic sorted so I will probably be more interested/busy with that in the near future

 

It'd certainly be nice to have this sort of challenge again Perhaps next time there could be several components to the challenge with varying degrees of complexity or varying subject areas? I imagine there are many things where you could have a basic fundamental maths component first, then perhaps a programming exercise and then perhaps some kind of analysis exercise or something, I don't know, I haven't really thought it out fully but I'm just chucking the idea out as it might get more people involved.

[bascule]

I'd be much more interested in a challenge if it were open to more languages. I have something of a pet peeve regarding Java. However I do enjoy golf (i.e. writing the shortest program possible) and like to submit entries in multiple languages.

[Cap'n Refsmmat]

It's hard to make direct performance comparisons when there are several languages in use.