I need to find out the fastest way to count nested loops. I am adding 3 numbers , the final number is wanted result. For better explanation here is example
read number 1
read number 2
read final number 3
There are 17 ways how to achieve 500 with those two numbers e.g
10*2 + 15*32
and so on , the code for this is pretty simple
i_max=final_number/number1
j_max=final_number/number2
for(i=0;i<i_max;i++){
for(j=0;j<j_max;j++){
count=number1 * i;
count_two = number 2 * j;
if(count+count_two==final_number){
//print it
}
}}
This code works fine , but the problem is when i input large numbers like
number1=100
number2=500
final_number=50000000
in this case , the computer takes very long time to count/find/print all possible ways. Is there any way to make alghoritm for this as fast for big numbers too? I have found out that the better way and fastest is not to increment i by 1 but by whole number or whole number /2 and sometimes both of them ; but how can i decide if i should add whole number or just half of the number to the i/j?
I tred to write in as much in pseudo code as i could
Also , i find out the second loop does not have to start always from 0/max number everytime it gets triggered , so
for i=0 ; i<max_number1;i++
for j=max_number2;j>=0;j--
if number1*i + number2*j == final number
max_number 2 = j
But i still fail to find when should i add whole number and when just half of it, I tried to increment first number by half of number2 , and second number by 1 until it finds match and then adding whole numbers , but this didnt work as i expected it worked for larger numbers but for numbers like
10
13
100
it said there is now way to combine first two and make 100 while there is a one
10 * 10 + 13 * 0
On request / for those who got lost in my explanation = i input 3 random numbers e.g 10 13 749 and i want to find out how many combinations of first two nubmers
10
13
would get result 749
it made it with nested loops
for(j=0;j<j_max;j++){
count=number1 * i;
count_two = number 2 * j;
if(count+count_two==final_number){
//print it
}
}}
which works but takes very long time to calculate if i input large numbers , for things i have tried or come up with read whole post.
Full example = number 1=757 number 2=989 final number = 56899148 There is 77 way how to combine first two numbers into the final one and those are
757 * 0 + 989 * 57532
757 * 989 + 989 * 56775
757 * 1978 + 989 * 56018
757 * 2967 + 989 * 55261
757 * 3956 + 989 * 54504
757 * 4945 + 989 * 53747
757 * 5934 + 989 * 52990
757 * 6923 + 989 * 52233
757 * 7912 + 989 * 51476
757 * 8901 + 989 * 50719
757 * 9890 + 989 * 49962
757 * 10879 + 989 * 49205
757 * 11868 + 989 * 48448
757 * 12857 + 989 * 47691
757 * 13846 + 989 * 46934
757 * 14835 + 989 * 46177
757 * 15824 + 989 * 45420
757 * 16813 + 989 * 44663
757 * 17802 + 989 * 43906
757 * 18791 + 989 * 43149
757 * 19780 + 989 * 42392
757 * 20769 + 989 * 41635
757 * 21758 + 989 * 40878
757 * 22747 + 989 * 40121
757 * 23736 + 989 * 39364
757 * 24725 + 989 * 38607
757 * 25714 + 989 * 37850
757 * 26703 + 989 * 37093
757 * 27692 + 989 * 36336
757 * 28681 + 989 * 35579
757 * 29670 + 989 * 34822
757 * 30659 + 989 * 34065
757 * 31648 + 989 * 33308
757 * 32637 + 989 * 32551
757 * 33626 + 989 * 31794
757 * 34615 + 989 * 31037
757 * 35604 + 989 * 30280
757 * 36593 + 989 * 29523
757 * 37582 + 989 * 28766
757 * 38571 + 989 * 28009
757 * 39560 + 989 * 27252
757 * 40549 + 989 * 26495
757 * 41538 + 989 * 25738
757 * 42527 + 989 * 24981
757 * 43516 + 989 * 24224
757 * 44505 + 989 * 23467
757 * 45494 + 989 * 22710
757 * 46483 + 989 * 21953
757 * 47472 + 989 * 21196
757 * 48461 + 989 * 20439
757 * 49450 + 989 * 19682
757 * 50439 + 989 * 18925
757 * 51428 + 989 * 18168
757 * 52417 + 989 * 17411
757 * 53406 + 989 * 16654
757 * 54395 + 989 * 15897
757 * 55384 + 989 * 15140
757 * 56373 + 989 * 14383
757 * 57362 + 989 * 13626
757 * 58351 + 989 * 12869
757 * 59340 + 989 * 12112
757 * 60329 + 989 * 11355
757 * 61318 + 989 * 10598
757 * 62307 + 989 * 9841
757 * 63296 + 989 * 9084
757 * 64285 + 989 * 8327
757 * 65274 + 989 * 7570
757 * 66263 + 989 * 6813
757 * 67252 + 989 * 6056
757 * 68241 + 989 * 5299
757 * 69230 + 989 * 4542
757 * 70219 + 989 * 3785
757 * 71208 + 989 * 3028
757 * 72197 + 989 * 2271
757 * 73186 + 989 * 1514
757 * 74175 + 989 * 757
757 * 75164 + 989 * 0
Again this works , but with very big numbers it takes lot of time to actually calculate it.
10*2
, what does the second term have to look like? Is this true if you replace2
with any other number? If not, which values is it true for? Note that code is off-topic here; please replace the code with ideas and/or algorithms (pseudocode) . $\endgroup$ – D.W.♦ Nov 7 '15 at 9:44