View Full Version : Speed Question

Shawn Curry
Oct 27th, 2002, 03:27 AM
I'm still working on that numbers class. I'm dam proud of that thing!! It can do irrational division now (like 1 div by 7). I'm working on a pattern matching function for it now so it can identify when its a repeating number, and I know how im gonna do it too(pretty cool for my first big prog).

Anyway it got me thinking.. The heart of the program is it's conversions. It takes a character and subtracts 48 to turn it into an integer, and adds 48 to an integer to convert it to a char.

This and the constructors probably get the most calls of the whole program(this probably gets more). The integer conversion looks just like the character conversion, and that will have to remain how it is, but im wondering if I can make the character conversion faster.

Right now, its this:

char convert(int in)
char output = (in + 48);
return output;

I'm thinkin about doing this:

char convert(int in)
char* num = "0123456789";
return num[in];

This way it never even has to add. Which do you think would be faster?

Oct 27th, 2002, 08:28 PM
Not to be a stickler or anything but...

1 divided by 7 is not irrational division, 1 divided by the sqaure root of 7 is, the other is strictly division.

Just thought I'd be a pain in the butt about it. :D

Also, what language are you using? Java? Why not use parseInt to convert a char to an int???

Shawn Curry
Oct 28th, 2002, 02:01 AM
Im using MSVC++ Intro Ed 6. I think Java has a BigInteger and BigDecimal class, so i've heard. I'm really just doing it b/c its a really good learning tool for me. I'm in school for it now but I've been teaching myself for about 4 months now and this is really my first original idea I've taken from design to execution.

BTW 1/7 (one seventh) = 0.142857142857142857142857...infinity

in other words its an irrational number but we can represent it as:


which is what it does now. It stops at 200 digits if its an irrational number, it feeds it into my pattern matcher and it extracts the pattern that starts the earliest in the number

In other words:


it knows to take 12345 instead of 23451 or 34512.

Pretty cool huh?

Oct 28th, 2002, 11:29 AM
Sorry, again I must insist that 1/7 is not an irrational number.

By mathematical definition an irrational number is any number (n)that cannot be represented in the following form.

where a, b are integers and b !=0 , n = a/b.

Thus in your example 1/7: a= 1, b =7. The number is not irrational.

However, the number: square root of 2, cannot be represented in the form a/b where a & b are intergers and b!=0. So the square root of 2 is irrational.

Then we have trancendental numbers which include the likes of pi! But that's a whole new ball of wax.

To sum, 1/7 is not an irrational number.

Shawn Curry
Oct 28th, 2002, 01:33 PM
Ok ok. I guess i'm using the elementary definition of irrational. What was trying to say is that it is a number which has no definate stopping point, it just goes on and on forever.

But, I can approximate IRRATIONAL numbers to a given precision. My algorithm extracts 1000 digits / sec (I timed it) on a P4 1.8. There is also very little speed difference when the divisor < 100 digits. The speed is unaffected by the dividend length.

Oct 28th, 2002, 03:15 PM
That's pretty cool. I once created a program that would find Mersenne primes, only ran into problems once numbers couln't be represented in 32 bits. :P But I noticed on a P1 66Mhz, it took about 6 minutes to find the first 9, on a P4 1.7 about 1 sec. What a difference!

Shawn Curry
Oct 29th, 2002, 06:11 AM
The reason I started to build this was for large prime numbers. I used my base class (Whole numbers) to build the Sieve of Erosthanes(an elementary method of computing primes). I had this independant research assignment about computer encryption codes and it said that it was nearly impossible to compute 200 digit primes, so I just had to try. Turns out it is pretty difficult. The first prototype was able to extract all the primes under 1,000 in the blink of an eye, but the higher you go the slower it goes. Took about 10 mins to compute all under 10,000. The next one was smarter(it used a queue so it was only checking exactly as many primes as it needed to) but it still took about 7 mins to get up to 10,000. I had some ideas about how to get up to 200, namely to start at a 200 digit number and use the queue more like a stack(clear it out as goes along to save memory) but I think it still would have taken days just to confirm one 200 digit prime. It would probably eliminate a whole bunch in a hurry, but it would have do divide by billions of different numbers when it ran into a prime.

Anyhow, I've been working all day on getting this decimal straight on my division algorithm. It gets all the numbers right, and it gets the decimal point right about 75% of the time. It seems so simple, but I'm on my fourth complete rewrite of the algorithm, and I cant even count how many times i've rewritten the decimal point logic.


Oct 29th, 2002, 11:34 AM
We are doing this in our APCS class. We also have previously written a Rational number class.

Which means, on top of BigInt, we will be able to do:


to represent basically any Rational number you could possibly work with.

Just a speed note:
Adding and subtracting 48 is going to be slow after a while. Create an enumerable type and go through that instead. Looking up what is at a memory address is faster than addition/subtraction.

Shawn Curry
Oct 30th, 2002, 12:39 AM
Yeah I thought about that too. I may put that char array at global scope so it only initializes it once. All my algorithms are still pretty darn quick, though. My division algorithm extracted 3000 digits in 0.83 seconds this morning. It can get 500 just as fast as I can hit enter to debug it, and that's dividing 2 decimal numbers.

And I'm in my first quarter in school. We dont even have an APCS program, and I'm not going to be in any programming classes until my third quarter. So I can't even ask for help when I need it. Ah well, I'm going to end up writing 4 different division algorithms for that decimal place and only use the operator as a logic shell. I can't figure out a good way to generalize the logic for the decimal placement. I can get it to work for each different case, but when i change something other cases stop working. #p

It'll be really cool when its done though ! :)