# Finding the Original Fractions from Rounded Decimals

The data I'm using is summoning rates from a gacha game, One Piece Treasure Cruise. The game provides the probability of getting a certain character in percents rounded to the nearest thousandth. However, the data does not sum to 100%, so I want to find the original fractions used to calculate those decimals.

I've programmed a brute force approach to find these ratios. It iterates through potential numerators for each sub-category of data. If the results match all given in-game output, it gets displayed. The problem is that it takes a long time to run, so I need help optimizing it. I'm certain that there are better ways to do what I'm attempting.

In the game, characters in this particular dataset are divided into three rarity categories: 5 Star, 4 Star, and 3 Star. Each character also has one of six types (STR, DEX, QCK, PSY, or INT). Within the 5 Star and 4 Star categories, there are 4 subgroups, each with different probabilities. I added some comments to clarify parts of the code.

double round5places(double input);

int main() {

double given5rate = 0.07089; // The in-game rate for summoning a 5 star char
double given4rate = 0.72911;
double given3rate = 0.2;

double givenSTR = 0.19934; // The in-game rate for summoning a STR char
double givenDEX = 0.13355;
double givenQCK = 0.25456;
double givenPSY = 0.2124;
double givenINT = 0.20014;

double denom = 1;  // The denominator of the fractions (iterates to 1,000,000)

double given5_1 = 0.00182; // The in-game rate for a sub-group of the 5 star characters
double cat5_1 = 0; // The category's numerator that will be iterated
double num5_1 = 1; // The number of characters in this subset

double given5_2 = 0.00016;
double cat5_2 = 0;
double num5_2 = 12;

double given5_3 = 0.00222;
double cat5_3 = 0;
double num5_3 = 5;

double given5_4 = 0.00043;
double cat5_4 = 0;
double num5_4 = 129;

double given4_1 = 0.01818;
double cat4_1 = 0;
double num4_1 = 1;

double given4_2 = 0.00156;
double cat4_2 = 0;
double num4_2 = 11;

double given4_3 = 0.02218;
double cat4_3 = 0;
double num4_3 = 5;

double given4_4 = 0.00435;
double cat4_4 = 0;
double num4_4 = 134;

double given3_1 = 0.02222;
double cat3_1 = 0;
double num3_1 = 9;

double sum5 = 0;
double sum4 = 0;
double sum3 = 0;

double sumSTR = 0;
double sumDEX = 0;
double sumQCK = 0;
double sumPSY = 0;
double sumINT = 0;

for (denom = 1; denom <= 1000000; ++denom) {
for (cat5_1 = 1; cat5_1 < denom; ++cat5_1) {
if (given5_1 == round5places(cat5_1 / denom)) {
// If the fraction for the first sub-category of 5 stars matches the posted in-game rate, start working on the next sub-category
for (cat5_2 = 1; cat5_2 < denom - cat5_1; ++cat5_2) {
if (given5_2 == round5places(cat5_2 / denom)) {
for (cat5_3 = 1; cat5_3 < denom - cat5_1 - cat5_2; ++cat5_3) {
if (given5_3 == round5places(cat5_3 / denom)) {
for (cat5_4 = 1; cat5_4 < denom - cat5_1 - cat5_2 - cat5_3; ++cat5_4) {
if (given5_4 == round5places(cat5_4 / denom)) {
sum5 = num5_1 * (cat5_1 / denom) + num5_2 * (cat5_2 / denom) + num5_3 * (cat5_3 / denom) + num5_4 * (cat5_4 / denom);
if (given5rate == round5places(sum5)) {
for (cat4_1 = 1; cat4_1 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4; ++cat4_1) {
if (given4_1 == round5places(cat4_1 / denom)) {
for (cat4_2 = 1; cat4_2 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4 - cat4_1; ++cat4_2) {
if (given4_2 == round5places(cat4_2 / denom)) {
for (cat4_3 = 1; cat4_3 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4 - cat4_1 - cat4_2; ++cat4_3) {
if (given4_3 == round5places(cat4_3 / denom)) {
for (cat4_4 = 1; cat4_4 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4 - cat4_1 - cat4_2 - cat4_3; ++cat4_4) {
if (given4_4 == round5places(cat4_4 / denom)) {
sum4 = num4_1 * (cat4_1 / denom) + num4_2 * (cat4_2 / denom) + num4_3 * (cat4_3 / denom) + num4_4 * (cat4_4 / denom);
if (given4rate == round5places(sum4)) {
for (cat3_1 = 1; cat3_1 < denom - cat5_1 - cat5_2 - cat5_3 - cat5_4 - cat4_1 - cat4_2 - cat4_3 - cat4_4; ++cat3_1) {
if (given3_1 == round5places(cat3_1 / denom)) {
sum3 = num3_1 * (cat3_1 / denom);
if (given3rate == round5places(sum3)) {
if ((sum5 + sum4 + sum3) == 1.0) {
sumSTR = 1.0 * (cat3_1 / denom) + 3.0 * (cat4_2 / denom) + 37.0 * (cat4_4 / denom) + 4.0 * (cat5_2 / denom) + 35.0 * (cat5_4 / denom);
if (givenSTR == round5places(sumSTR)) {
sumDEX = 1.0 * (cat3_1 / denom) + 1.0 * (cat4_2 / denom) + 23.0 * (cat4_4 / denom) + 1.0 * (cat5_2 / denom) + 23.0 * (cat5_4 / denom);
if (givenDEX == round5places(sumDEX)) {
sumQCK = 2.0 * (cat3_1 / denom) + 2.0 * (cat4_2 / denom) + 29.0 * (cat4_4 / denom) + 2.0 * (cat4_3 / denom) + 1.0 * (cat4_1 / denom) + 2.0 * (cat5_2 / denom) + 26.0 * (cat5_4 / denom) + 2.0 * (cat5_3 / denom) + 1.0 * (cat5_1 / denom);
if (givenQCK == round5places(sumQCK)) {
sumPSY = 3.0 * (cat3_1 / denom) + 1.0 * (cat4_2 / denom) + 24.0 * (cat4_4 / denom) + 1.0 * (cat4_3 / denom) + 1.0 * (cat5_2 / denom) + 25.0 * (cat5_4 / denom) + 1.0 * (cat5_3 / denom);
if (givenPSY == round5places(sumPSY)) {
sumINT = 2.0 * (cat3_1 / denom) + 4.0 * (cat4_2 / denom) + 21.0 * (cat4_4 / denom) + 2.0 * (cat4_3 / denom) + 4.0 * (cat5_2 / denom) + 20.0 * (cat5_4 / denom) + 2.0 * (cat5_3 / denom);
if (givenINT == round5places(sumINT)) {
std::cout << "Denominator: " << denom << "\n5-1: " << cat5_1 << "\n5-2: " << cat5_2 << "\n5-3: " << cat5_3 << "\n5-4: " << cat5_4 << "\n4-1: " << cat4_1 << "\n4-2: " << cat4_2 << "\n4-3: " << cat4_3 << "\n4-4: " << cat4_4 << "\n3-1: " << cat3_1;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}

return 0;

}

double round5places(double input) {
return (round(input * 100000.0) / 100000.0);
}


If I'm not mistaken, the question stated in the title isn't the question you ask in your post's body. Finding the nearest rational approximation of a double-precision number is one thing, mirroring the character selection of a game another.

As to the first one, a fairly good answer is based on the Farey sequence, which will converge quicker than brute-force in most cases. It works on numbers between 0 and 1, thus it is well adapted to probabilities. Here's a fairly basic adaptation:

struct Farey_fraction {
unsigned numerator, denominator;
Farey_fraction(unsigned n, unsigned d) : numerator(n), denominator(d) {}
operator double() const { return numerator / static_cast<double>(denominator); }
};

Farey_fraction mediant(Farey_fraction lhs, const Farey_fraction& rhs) {
return Farey_fraction(lhs.numerator + rhs.numerator, lhs.denominator + rhs.denominator);
}

Farey_fraction nearest_rational(double target, std::size_t maximum_denominator) {
Farey_fraction min{0, 1}, max{1, 1};
// unless you can find a rational representation of the target
// return the neighboring fraction with the greatest allowed denominator
while (min.denominator <= maximum_denominator && max.denominator <= maximum_denominator) {
auto guess = mediant(min, max);
if (guess == target) {
if (min.denominator + max.denominator <= maximum_denominator) return guess;
else if (max.denominator > min.denominator) return max;
else return min;
}
// update the bounds to converge
else if (target > guess) min = guess;
else                     max = guess;
}
if (min.denominator > maximum_denominator) return max;
return min;
}


Once you have solved this problem, you have a quite direct solution to the second one: you only need to distribute the difference between 1 and the sum of the rational approximations between the approximations to reconstitute the 100% total. There's a little bit of work here, since you might have to simplify fractions. I you use C++17 you can rely on std::gcd to make the task easier.

1. constants should be const. To the very least; you can constexpr them also (for instance: constexpr double given5rate = 0.07089;. It expresses your intent better, and will trigger a compilation error if you modify it by mistake.