I need to "factorize" some non-integer product to multipliers from the set ([0, 25] with step 0.25). The number of multipliers is chosen (2 to 5). Ideally results should be slightly different each run (and not contain only 1's with product). The result should be within 0.1 of the initial product.
For example: Factor out 12.5 to 3 multipliers = 4.75 * 3.5 * 0.75 = 12.468. Close enough. Next run it could be 14.25 * 1.75 * 0.5 = 12.468.
Right now my solution is finding pairs that give desired product but it is not exactly what i want.
The multipliers to choose from (0 to 25 with 0.25 increments) can be turned into integers by multiplying them by 4, which gives 0 to 100.
Apply the same "multiply by 4" to the value to factor, but for each such multiplier. So for 3 multipliers, apply 4*4*4 or 4^3.
By changing everything to integers, testing for valid factors becomes trivial (the remainder of an integer division = 0).
Then generate all combinations that result in de desired factor, and randomly pick one result from that list.
I've coded up a quick & dirty example in C++ which ignores boring factors (the value itself and 1).
#include <array>
#include <iostream>
#include <random>
#include <vector>
void findFactorsBy4(const int input, const int remainder, const int stepsLeft, std::array<int,3>& steps, std::vector<std::array<int,3>>& results)
{
if (stepsLeft < 1)
{
return;
}
if (stepsLeft == 1)
{
// skip factors that boil down to 1
// skip factors that match the input
// only use factors within range now
if (remainder != 4 && remainder != input && remainder > 0 && remainder <= 100)
{
// found suitable option
steps[0] = remainder;
// add option to results
results.push_back(steps);
}
}
else
{
// check factors from 0 to 25 with 0.25 increments (but multiplied by 4), excluding 0
for (int i = 100; i > 0; i--)
{
// skip factors that boil down to 1
// skip factors that match the input
if (i != 4 && i != input && remainder % i == 0)
{
// found suitable option
steps[stepsLeft-1] = i;
// go find next factor
findFactorsBy4(input, remainder/i, stepsLeft-1, steps, results);
}
}
}
}
void printResult(const std::array<int, 3>& steps)
{
for (const auto n : steps)
{
std::cout << n/4.0 << ' ';
}
std::cout << '\n';
}
int main()
{
int numberOfFactors = 3;
double input = 12.5;
int intInput = input * 4; // 12,5 * 4 (only used to ignore boring factors)
int intRemainder = input * pow(4,numberOfFactors); // 12,5 * 4^3
std::cout.precision(3);
std::cout << "Finding " << numberOfFactors << " factors for " << input << "...\n";
std::array<int,3> steps;
std::vector<std::array<int,3>> results;
findFactorsBy4(intInput, intRemainder, numberOfFactors, steps, results);
std::cout << "Found " << results.size() << " factors:\n";
// print them all
for (auto const& res : results)
{
printResult(res);
}
// randomly pick one
std::cout << "Randomly picked one result:\n";
std::random_device rd; // obtain a random number from hardware
std::mt19937 gen(rd()); // seed the generator
std::uniform_int_distribution<> distr(0, results.size()-1); // define the range
printResult(results[distr(gen)]);
}
Output:
Finding 3 factors for 12.5...
Found 63 factors:
0.25 2 25
2 0.25 25
0.25 2.5 20
0.5 1.25 20
1.25 0.5 20
2.5 0.25 20
0.25 5 10
0.5 2.5 10
2.5 0.5 10
5 0.25 10
0.25 6.25 8
1.25 1.25 8
6.25 0.25 8
0.25 8 6.25
0.5 4 6.25
4 0.5 6.25
8 0.25 6.25
0.25 10 5
0.5 5 5
1.25 2 5
2 1.25 5
5 0.5 5
10 0.25 5
0.5 6.25 4
1.25 2.5 4
2.5 1.25 4
6.25 0.5 4
0.25 20 2.5
0.5 10 2.5
1.25 4 2.5
2 2.5 2.5
2.5 2 2.5
4 1.25 2.5
10 0.5 2.5
20 0.25 2.5
0.25 25 2
1.25 5 2
2.5 2.5 2
5 1.25 2
25 0.25 2
0.5 20 1.25
1.25 8 1.25
2 5 1.25
2.5 4 1.25
4 2.5 1.25
5 2 1.25
8 1.25 1.25
20 0.5 1.25
1.25 20 0.5
2.5 10 0.5
4 6.25 0.5
5 5 0.5
6.25 4 0.5
10 2.5 0.5
20 1.25 0.5
2 25 0.25
2.5 20 0.25
5 10 0.25
6.25 8 0.25
8 6.25 0.25
10 5 0.25
20 2.5 0.25
25 2 0.25
Randomly picked one result:
0.5 2.5 10
Live example: https://godbolt.org/z/PaPrqdYfb
[edit]
As noted by btilly, this does not work great for inputs that do not line up nicely with the multipliers to choose from.
An implementation with floating point numbers (but still using integers to determine the multipliers, and a bit of cheating with factor of 4 to keep the result within the given threshold of 0.1):
#include <array>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
constexpr double THRESHOLD = 0.1;
void findFactors(const double threshold, const double remainder, const int stepsRemaining, std::vector<double>& factorSteps, std::vector<std::vector<double>>& results)
{
if (stepsRemaining < 1)
{
return;
}
if (stepsRemaining == 1)
{
// only use factors within range now
if (remainder > 0.0 && remainder <= 25.0)
{
// check if remainder within (scaled) threshold of a factor
int lowerInt = static_cast<int>(floor(remainder * 4.0)); // force truncation to int
double lowerDouble = lowerInt/4.0;
// skip factors that boil down to 1
if (lowerInt != 4 && lowerInt > 0 && std::abs(1.0 - remainder/lowerDouble) < threshold)
{
// found suitable multiplier
factorSteps[0] = lowerDouble;
// add option to results
results.push_back(factorSteps);
}
else
{
int upperInt = lowerInt+1;
double upperDouble = upperInt/4.0;
// skip factors that boil down to 1
if (upperInt != 4 && std::abs(1.0 - remainder/upperDouble) < threshold)
{
// found suitable multiplier
factorSteps[0] = upperDouble;
// add option to results
results.push_back(factorSteps);
}
}
}
}
else
{
// check factors from 0 to 25 with 0.25 increments (but multiplied by 4), excluding 0
for (int i = 100; i > 0; i--)
{
// skip factors that boil down to 1
if (i != 4)
{
// found suitable multiplier
double multiplier = i / 4.0;
factorSteps[stepsRemaining-1] = multiplier;
// go find next factor
findFactors(threshold, remainder/multiplier, stepsRemaining-1, factorSteps, results);
}
}
}
}
void printResult(const std::vector<double>& factorSteps)
{
for (const auto n : factorSteps)
{
std::cout << std::setprecision(2) << std::fixed << n << ' ';
}
std::cout << '\n';
}
void printResultProduct(const std::vector<double>& factorSteps)
{
double product = 1.0;
for (const double factor : factorSteps)
{
product *= factor;
}
std::cout << "Product from random result: " << std::setprecision(10) << std::fixed << product << '\n';
}
int main()
{
int numberOfFactors = 3;
double input = 4.94;
std::cout << "Finding " << numberOfFactors << " factors for " << input << "...\n";
// only checking the last multiplier to see if the result is within the threshold. Scale it down to match.
double threshold = THRESHOLD;
for (int i = 0; i < numberOfFactors-2; i++) // not sure why this needs to be -2 instead of -1
{
threshold *= THRESHOLD;
}
std::vector<double> steps;
steps.resize(numberOfFactors);
std::vector<std::vector<double>> results;
findFactors(threshold, input, numberOfFactors, steps, results);
if (results.empty())
{
std::cout << "No factors found!\n";
}
else
{
if (results.size() <= 20)
{
std::cout << "Found " << results.size() << " factors:\n";
// print them all
for (auto const& res : results)
{
printResult(res);
}
}
else
{
std::cout << "Found " << results.size() << " factors.\n";
}
std::cout << "Randomly picked one result:\n";
std::random_device randomDevice; // obtain a random number from hardware
std::mt19937 generator(randomDevice()); // seed the generator
std::uniform_int_distribution<std::size_t> distribution(0, results.size()-1); // define the range
// randomly pick one
std::vector<double> result = results[distribution(generator)];
printResult(result);
printResultProduct(result);
}
}
Output:
Finding 3 factors for 4.94...
Found 66 factors.
Randomly picked one result:
1.75 0.75 3.75
Product from random result: 4.9218750000
Live example: https://godbolt.org/z/9bbP9eYrK