-2

Following is the code I wrote for approximating the value of 103993/33102. The user inputs the precision. Here k is the precision inputted by the user and asd is the value in the form of a string

int tot = 4687;
int divisor = 33102;
StringBuffer fraction=new StringBuffer();
int tmp = tot;
    for(long i=1;i<=k;i++)
    {
        tmp = tmp*10;
        int res = tmp/divisor;
        fraction.append(res);
        tmp = tmp - res*divisor;
    }
    asd="3."+fraction.toString();

However when the user inputs a precision of 10^6 it takes enormous amount of time. The time limit is given 1 sec. Help!

Abhiroop Sarkar
  • 2,251
  • 1
  • 26
  • 45
  • How much time do you think it should take to compute (and store) 10^6 decimals? – SJuan76 Mar 03 '13 at 20:00
  • Its a codechef question and the time limit given is 1 sec. I tried with BigDecimal but that too takes enormous amount of time... – Abhiroop Sarkar Mar 03 '13 at 20:04
  • Think parallel, go use POSIX and another aproach to aproximate more adecuate to parallel algorithm, like http://stackoverflow.com/questions/10890613/fast-algorithm-to-calculate-pi-in-parallel – Ricardo Ortega Magaña Mar 03 '13 at 20:04
  • How many accounts are you duplicating all your questions under? This is madness. – Perception Mar 03 '13 at 20:05
  • I would 'cheat' by preassigning memory. Use a char[10^6] instead of StringBuffer, move the last line (conversion to String) outside the timing, and see what happens. – SJuan76 Mar 03 '13 at 20:07
  • possible duplicate of [Decimal expansion program running very slow for large inputs](http://stackoverflow.com/questions/15176872/decimal-expansion-program-running-very-slow-for-large-inputs) – Perception Mar 03 '13 at 20:07
  • @perceptron i have only 1 account possibly the other person is also trying to solve the same problem in codechef – Abhiroop Sarkar Mar 03 '13 at 20:10
  • Yeah,StringBuffer will chew up a substantial amount of time (though pre-allocating it to the expected size (`new StringBuffer(1000000)`) will help enormously). – Hot Licks Mar 03 '13 at 20:11
  • Can you give us the `BigDecimal` code? That should work at least as well as what you're doing, but if it's taking longer than this version, then you're probably doing something wrong there. – Louis Wasserman Mar 03 '13 at 20:15

2 Answers2

2

Your algorithm looks fine. StringBuffer is thread safe and therefore quite slow because it acquires a lock for each call to append. Use StringBuilder, and construct it with the capacity you know you'll need, i.e. k. This prevents multiple copies of the data as the buffer inside StringBuilder is expanded to accomodate the growing string.

This is clear if you read the StringBuffer docs:

As of release JDK 5, this class has been supplemented with an equivalent class designed for use by a single thread, StringBuilder. The StringBuilder class should generally be used in preference to this one, as it supports all of the same operations but it is faster, as it performs no synchronization.

Since you know the exact size of the output in advance, you can also use an array of bytes to hold the digits. Still final conversion to a string of length 10^6 and output are expensive. When I run the code below, it takes only 0.016 seconds to create the byte array, 0.06 to convert to a string, and over 1 second to print. To make progress, you will have to do some research on how to do fast i/o in Java. If you swith to C or another language closer to the hardware, the normal i/o routines may be fast enough.

public void run() {
    int k = 1000000;
    long start = System.currentTimeMillis();
    int tot = 4687;
    int divisor = 33102;
    byte [] buf = new byte[k];
    int tmp = tot;
    for (int i = 0; i < k; i++) {
        tmp = tmp * 10;
        int res = tmp / divisor;
        buf[i] = (byte)(res + '0');
        tmp = tmp - res * divisor;
    }
    System.out.println((System.currentTimeMillis() - start) * .001);
    String s = new String(buf);
    System.out.println((System.currentTimeMillis() - start) * .001);
    System.out.print("3."); System.out.println(s);
    System.out.println((System.currentTimeMillis() - start) * .001);
}
Gene
  • 46,253
  • 4
  • 58
  • 96
  • You must have run this from Eclipse or similar. From the command line it is done in 200 milliseconds. The bottleneck is not Java's I/O, but Eclipse's *capturing* of the same, and updating the Console text area. – Marko Topolnik Mar 03 '13 at 20:59
  • BTW like any rational number, this one's decimal expansion is periodical, and the point where a new period starts is easy to detect. This can be leveraged to just copy the periodic part with no further calculation. With a properly warmed-up JVM, the whole thing would take something like a millisecond. – Marko Topolnik Mar 03 '13 at 21:04
  • Netbeans, but you're right. Still 200 ms is 12 times the computation itself. I'm pretty sure a direct call to the system's `write` with the byte buffer would be faster. – Gene Mar 03 '13 at 21:05
  • You don't even need any arrays: print each digit directly as you calculate it. – Marko Topolnik Mar 03 '13 at 21:06
  • Of course. But his spec of 1 second is easily met without the trouble. – Gene Mar 03 '13 at 21:07
  • Sure, this is just for the fun of it :) Tested direct write without accumulating into a buffer, it's slower because the writes are too fine-grained. – Marko Topolnik Mar 03 '13 at 21:09
  • A direct `write(byte[])` call gives overall 100 ms; but if you don't print anything (redirect standard output to a file), then the runtime is 20 ms. – Marko Topolnik Mar 03 '13 at 21:15
0

Preallocate the value in a very big string, and just make a substring of K elements, so you dont have to calculate each time, and the result will be in an instant.

Ricardo Ortega Magaña
  • 2,403
  • 16
  • 23