Optimizing algorithm

Development Code
1

Hello there...

I'm legolizard, and I've been watching the tek syndicates' videos for a while now, and thought it would be a good idea to finally join the forum. :D It really is awesome, I must say...

 

I was wondering if anyone could help with an algorithm I'm designing. It's mainly for the giggles. I mean, who doesn't like seeing lines and lines of numbers strung across the console window in an endless furry of some computational mess?

 

I've written this program in C++; it is relatively simple, yet I wish to optimize it so that it will output the answer faster. To outline the basic goal of the program:

Find all the differnt series of numbers that are the summation of a set number, n. For example, assuming the user enters in five the ouput would be:

1 4

2 3

5

 

For small n my current method is super fast, but that's not much of an accomplishment, lawl. For n > 40 the process can take up to a minute+. 

Could anyone offer some advice on how to optimize my current method? 

 

My current function:

 

void getSums( const std::string &str, int x, int y ){


for( ; x >= 2 * y + 1; y++ ) getSums( str + ' ' + toString(y), x - y, y + 1 );
std::cout << str << ' ' << x << std::endl;


}

 

I know that seems kind of... weird at first, I asked my CS teacher and he gave me ?_? face. It really isn't all too complicated though... at least from my point of view it isn't... then again I spent days thinking about it, lawl.

toString is a function I declared earlier in the program to parse an integer data type to a string(Templates ftw).

Any help would be appreciated. Thanks. :D Oh and thanks for this awesome forum. ^_^

 

 

 

2

Dang, I wish I could help you, my background is in C# though so your example doesn't help me all that much and I'm mathematically... crap anyway.

Hang on.

I might have thought of something. Let me just get back to you.

3

#include <iostream>
#include <string>
int main()
{
int input;
std::cin>>input;
std::string results;
    for(int i = 0; i < input/2; i++)
    {
        std::cout<<i<<" "<<input-i<<'\n';
    }
    return 1;
}

ran to 1000 in 3 seconds. if you need it to be crazy fast, i could get into openCL or asm optimizations, but thats a bit complex :)

4

edit: that format of the code went out of wack there

I wanted to give it a try. This only shows the sum of two numbers, so I guess it's not really what you were looking for, but a little exercise for me nonetheless.

#include <iostream>

int main()
{
int x;
int count = 0;
std::cin >> x;
for(int i = 0; i < x/2; ++i) {
++count;
std::cout << i << " " << x-i << std::endl;
}
if(x % 2 == 0)
   std::cout << count << " " << count << std::endl;
else
   std::cout << count << " " << count + 1 << std::endl;
return 0;
}

 

5

Nah, mine didn't work. Never mind.

6

ztrain has the right idea. Divide the limit of your loop by 2. For instance if im printing out all the numbers that sum to 6:

I print 6

I print 1 and 5

I print 2 and 4

I print 3 and 3

I print 4 and 2.... wait! No need! Ive already done that. This applies to 5 and 1 too.

 

Here is what I came up with in Java:

x is whatever the user inputs: ...3000 for example

 

long x = 3000;
       
        for (long i = 1; i <= x / 2; i++) {
            
            long y = x - i;
            
            if(i == 1){
                System.out.println(x + " = " + x);
            }
            
            System.out.println(y + " + " + i + " = " + x);
              
        }

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

Ran to 50000 in 4 seconds.

Ran to 1,000,000 in 1 min 38 seconds.

Ran to 1,000,000,000 in... Ill get back to you haha

Good post legolizard!

7

just some more insight on this: by using a system print, you cause your program to halt and have the output written to the screen. due to complexities and no code formatting, im not going to post the code for it, but write everything to a buffer, then print that at the end. just a simple array would do. also, if you want to go over the top, use openCL to compute it. 1,000,000,000 would take LESS THAN A SECOND using your gpu.

 

further, look up the colltaz congecture. thats a fun one to program for beginners.

8

you could start a binary tree that divides each input /2 step into its own leaf and the once it has generated a leaf that is down to the simplest input/2, you can recursively step back up the array. since i understand the basics of binary trees and recursion and not much about programming, i leave an Idea nugget for you to code. =) good luck!

9

I wrote a small program in c++ that does the collatz congecture and shows how many steps. Interesting how every positive number always goes to 1. I'm enjoying these little programs, making me exercise my brain.

#include <iostream>

using namespace std;

int main(){

unsigned long long n;
cin >> n;
cout << endl;

int count = 0;
while (n > 1){
cout << n << endl;
++count;
if(n % 2 != 0){
n = 3 * n + 1;
}
else
n = n / 2;
}
cout << n << endl <<"Total steps: " << count << endl;

return 0;
}

 

10

MULTITHREADING!!!!!!

idk if this works, i really don't know programming, but just assign different leaves to different cpu cores

11

Thank you so much guys for all your help. =) 

Chronic78 and SillyDuck(awesome name by the way), both of those methods are really interesting, and I suppose both are using the binary tree method that MegaDove is proposing; I never thought about this problem that way. I over looked the obvious duplicates the program made, mainly because I didn't want to sacrifice outputting all the different sets of numbers that are the summation of n. For example, for 15 the program would output not only sets of two (1 + 14, 2 + 13, etc), but also 1 + 2 + 3 + 4 + 5. Nevertheless, it is now possible to elimianate the duplicate sets, no matter how large it may be!

Also, ztrain, I will research the colltaz congecture... I believe I've heard about it, yet I don't trust my memory very much. Darn, SillyDuck beat me to it. X_X I'll see what I come up with.=) Oh, and I plan on learning OpenCL one day, right now I'm learning Assembly, but I couldn't write this program in Assembly... to much mov-ing, push-ing and pop-ing. XD

 Again, thanks for all your input guys. I've already been able to speed my function slightly, and now I think by deleting the duplicates it should run much faster. :D

 EDIT: 

Oh, sorry Commissar, you posted while I was still typing.... :( If only I knew how to do that...

12

lol, I can't even get as far as you did... all I know is HTML5 and CSS. can't really count yaml. done a bit with lua

13

Actually i don't really think multithreading would be good for this... threading is only good for concurrent tasks... but you would actually have to loop through numbers for this so i'm not sure multithreading would be efficient

14

http://codepad.org/yufCdlqE - since the recurrency is so simple limited only by i/o.

for example n = 100 - 444792 answers, generated in 0.4s on my home pc - but can still be improved by optimizing various parts:

1) custom number to string conversion: http://codepad.org/OYOOHMlH - runtime drops down to 0.09s,

2) buffer output: http://codepad.org/CLpJ3w5Q - runtime drops down to 0.04s.

15

That is actually really interesting; I never thought I would be bottlenecked by I/O.

Maybe my computer is just really slow though, since running 100 took much longer than .4 seconds.

Custom string and output sounds really interesting, though! It would, of course, be faster if the number was passed in by argument(like what you did), rather than via input. Well the overall time of the program would be much shorter.