Combinations - help with sorting duplicates

closed account (EUC9216C)
Im trying to generate a set of four numbers, each ranging from 1 to 200 for starters, but upper limit could be higher.
what i have now is 4 for loops:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
void findNumberSets(float ratio, float err, float lowerLimit, float upperLimit)
{
   int count = 0;
   float actualError = 0;
   for (float a = lowerLimit;a<=upperLimit;a++)
    {
        // Second Interation
        for(float b=lowerLimit;b<=upperLimit;b++)
        {
            //Third Iteration
            for(float c=lowerLimit;c<=upperLimit;c++)
            {
                //Fourth Iteration
                for(float d=lowerLimit;d<=upperLimit;d++)
                {
                    actualError = fabs((a*c)/(b*d) - ratio);
                    if( actualError <= err)
                    {
                        count++; // Found set within range
                    }
                }
            }
        }
}


You supply it a decimal and a error amount, and it counts every single possibility the 4 numbers can be in that will give a decimal within the range of "err".

Well with the upperLimit set higher, this functions takes longer and longer to execute. What I need though is a way to cut the number of loops by a quarter to speed it up.

If it returns four numbers, for example, a=21, b=30, c=100, d=150, there are three other identical ratios that I dont need to find. For example,
a=100, b=30, c=21, d=150
a=21, b=150, c=100, c=30,
a=100, b=150, c=21, d=30

I thought about storing every option in an array of sorts, but then checking through for matches each loop seems excessive, and may increase the time it takes to execute. As it is now, 4 sets from 1 to 200 yields a huge amount of results depending on the err wanted.

Can anyone shed some direction on this?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void findNumberSets(float ratio, float err, float lowerLimit, float upperLimit)
{
   int count = 0;
   float actualError = 0;
   for (float a = lowerLimit;a<=upperLimit;a++)
    {
        // Second Interation
        for(float b=lowerLimit;b<=upperLimit;b++)
        {
            //Third Iteration
            for(float c=a;c<=upperLimit;c++)
            {
                //Fourth Iteration
                for(float d=b;d<=upperLimit;d++)
                {
                    actualError = fabs((a*c)/(b*d) - ratio);
                    if( actualError <= err)
                    {
                        count++; // Found set within range
                    }
                }
            }
        }
   }
}


Perhaps?
closed account (EUC9216C)
No that doesnt work. The number of results was incorrect. I sadly dreamt about this last night, lol and think I came up with a soluction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
for (float d = lowerLimit;d<=upperLimit;d++)
    {
        // Second Interation
        for(float c=lowerLimit;c<=upperLimit;c++)
        {
            //Third Iteration
            for(float b=lowerLimit;b<=upperLimit;b++)
            {
                //Fourth Iteration
                for(float a=lowerLimit;a<=ceil((((b*d)*ratio)/c));a++)
                {
                    if ((a*c) >= (b*d))
                    {
                        continue;   // Fraction over one, go onto next one
                    }
                    actualError = fabs((a*c)/(b*d) - ratio);
                    if( actualError <= err)
                    {
                        // count the found one
                        count++;
                    }
                }
            }
        }
    }


It runs very fast, but seems to produce 8 more results than the previous method using 20,100 for upper and lower limits. Now Im just trying to compare the results and see where the differences are. If this new method works, I will be very happy with it.

Edit: I found I had a test in the for loop of "a<upperLimit" in one try and "a<=" in the other. I set all to <= and the results are identical, so I guess its a success.
Last edited on
Topic archived. No new replies allowed.