# fastest counting of nested loops

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


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.

• This is a nice exercise, but you should try to solve it yourself. Hint: If the first term is 10*2, what does the second term have to look like? Is this true if you replace 2 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) . – D.W. Nov 7 '15 at 9:44
• yes in this case its pretty obvious , but i need to find way how to make it fast for all inputs > 0 , in other cases its not so obvious and i fail to find the way – user3424358 Nov 7 '15 at 9:56
• OK -- then I suggest you edit the question to show what you've worked out so far and how far you got along that line where you got stuck... especially, which cases you can handle and which ones are not obvious to you. – D.W. Nov 7 '15 at 10:10
• From your question, it's not clear to me what the problem you are trying to solve is exactly. Please give a precise definition. – Raphael Nov 7 '15 at 11:08
• Examples are not a substitute for a concise and precise description. (Also, your title does not seem to relate to the problem you describe, at all.) – Raphael Nov 7 '15 at 23:48

With inputs $n_1,n_2,n_3$, you want to find all positive integers $(a,b)$ such that $an_1+bn_2 = n_3$ You observed that for even moderately large inputs, your two nested loops with a test to see if you come up with a solution takes a long time. It you apply a bit of number theory, there's an algorithm that is very much faster.

1. First, find the greatest common divisor of $n_1$ and $n_2$. The extended euclidean algorithm is not only very fast (using a number of steps proportional to the number of digits in the larger of the two numbers), but also provides a way to do the next step. If $g=\gcd(n_1,n_2)$ divides $n_3$, continue to the next step, otherwise there will be no solutions to your problem, so quit.
2. The extended Euclidean algorithm will give you integer solutions, $a, b$ to $$an_1+bn_2=g$$ In what follows, we'll assume $g=1$ for simplicity. If it's not, just divide $n_1,n_2,n_3$ by $g$ and carry on as below. We'll then have $$(an_3)n_1+(bn_3)n_2 = n_3$$ You're getting close to a solution, but $an_3$ or $bn_3$ might not both be positive, so we'll need some other solution. Observe that for any integer $k$, \begin{align} & (an_3-kn_2)n_1+(bn_3+kn_1)n_2\\ =&\ (an_3)n_1-kn_2n_1+(bn_3)n_2+kn_1n_2\\ =&\ (an_3)n_1+(bn_3)n_2 = n_3 \end{align} so $an_3-kn_2$ and $bn_3+kn_1$ will also be solutions, for any integer $k$.
3. Now all we have to do is pick $k$ values such that $$an_3-kn_2\ge 0\quad\text{and}\quad bn_3+kn_1\ge 0$$ In other words, all we have to do is loop through the integers $k$ such that $$-\frac{bn_3}{n_1}\le k\le\frac{an_3}{n_2}$$

Edit: There's a potential problem here, though: it might be that some of the intermediate calculations might be too large to avoid integer overflow. Let's see if we can keep everything no larger than $n_3$. We could let $k=a\lfloor n_3/n_2\rfloor$ and it's not hard to show that $$a'=an_3-kn_2=an_3-a\left\lfloor\frac{n_3}{n_2}\right\rfloor n_2>0$$ and then let $$b'=\frac{n_3-a'n_1}{n_2}$$ we will have found a solution, $(a',b')$ to $$a'n_1+b'n_2=n_3$$ which was our goal.

Here's how it would work for an example almost like yours with $n_1=989$, $n_2=757$, $n_3=56899150$.

First, find $\gcd(989,757)=1$, and we find from the extended Euclidean algorithm that $$1=(62)989+(-81)757$$ so we let \begin{align} a'&=62\left(56899150-757\left\lfloor\frac{56899150}{757}\right\rfloor\right)\\ &= 62(56899150-757\cdot75164)\\ &= 62(56899150-56899148)\\ &= 62\cdot 2 = 124 \end{align} and we also find that $b'=75002$, so we'll have solutions $(a',b')$ given by $$\begin{array}{cc} a' & b'\\ 124 & 75002 \\ 881 & 74013 \\ 1638 & 73924 \\ \vdots & \vdots \\ 56899 & 827 \end{array}$$ where each row in the solution is the previous row solution for $a'$ plus 757 and the previous row solution for $b'$ minus 989, stopping when the $b'$ solution is negative.

• as previous one great explanation , but what would be the result = amount of combinations? in this case it should be 76 – user3424358 Nov 10 '15 at 21:49
• In this example, once we find $(a',b')$, the $a'$ will be the smallest possible, so we require $b'>0$ and ask how many multiples of 989 will it take to drive $b'$ to its smallest positive value? Just divide $b'$ by 989, so $75002=(75)989+827$ so 75 steps will take $b'$ down as small as possible, plus 1 for the original $(a',b')=(124,75002)$ or, indeed 76 values, as you indicated. BTW, I've spent a lot of time on this, so if you find it helpful, it might be a good idea to reward me by clicking the green check mark to accept the answer. – Rick Decker Nov 10 '15 at 22:06
• hopefully last question how did u get the value of b`? with same method as for a its around 160 – user3424358 Nov 12 '15 at 20:05
• @user3424358. Since we know that $an_1+bn_2=1$ in this case, we have $b=(1-an_1)/n_2$ and we also know $b'=bn_3$. Take it from there. – Rick Decker Nov 12 '15 at 21:04
• im afraid , this method does not work either for big numbers if you wanted to try it - 5098109 , 25279297 ,36821491225502191 and 286 is should be result – user3424358 Nov 12 '15 at 22:25