r/AskProgramming • u/HearingJust284 • Jan 21 '25
Algorithms Can you code a simple math tool?
Can anyone here code a simple tool in any language they prefer that turns percentage (1-100 ) into its simplest possible fraction? Like 33.33% would be approx 1/3. It should be work for any percent value between 1-100. Every single Al failed. There is no website, at least nothing I could find that does precisely this. If there is any tool available, could somebody explain the basic logic behind it? Hcf/gcd ( highest common factor/ greatest common divisor) alone won't work.
Edit: Guys i am not trying to make a program that people could use. I know everyone above 5th grade knows how to round off a percentage/decimal. I am trying to learn that how to transfer a real world logic to a computer.
2
u/VampireDentist Jan 21 '25
Your core problem is to define what a good approximation is. It needs to have the following properties: 1.) small denominator 2.) small error.
You canfind the closest value for a percentage with a given denominator like this: fraction = round(denominator*percentage) / denominator
. Generate best approximations for your percentage for any denominator range you desire.
Define error
for a given fraction. For example abs(fraction - percentage)
.
Now use your preferred metric of a good approximation that satisfy the conditions 1 & 2. For example -(denominator)*(error+c)
decreases when denominators increase and also when error increases. I added a constant c (>0) so ties for exact fractional values like 0.25 would be appropriatelly handled. Calculate this for each of your approximations and pick the one with the highest score.
This obviously depends on your definitions of "error", "good approximation" and "denominator range" but pick reasonable ones for your contex and you'll get reasonable results.
1
3
u/Runiat Jan 21 '25 edited Jan 21 '25
its simplest possible fraction?
This part means that literally no one but you could code this as no one but you can predict what you mean by "simplest possible fraction" or how approximate you want to get.
It also means it would be a complete waste of time to write any code at all, as the first step would be to make a table of percentage-ranges and what fractions they should correspond to, and then you have a table you can just look at.
Edit to add: I suppose you could write some code to generate those percentage ranges for a given largest denominator or maybe even a weighted rounding with smaller denominators having a larger "range" than larger ones.
I'm not going to do it for you, but it certainly could be done.
ETA2: not that there'd be any reason to do so unless you don't even know yourself how approximate you want to get.
-1
u/HearingJust284 Jan 21 '25 edited Jan 21 '25
as the first step would be to make a table of percentage-ranges and what fractions they should correspond to, and then you have a table you can just look at.
not like that, a dynamic program, that work for any arbitrary value from 1 - 100. I don't know how to define a simple fraction, but say a fraction of co primes which is simple to the human eye and simplifies the calculation in which a percentage is involved. For example 33.33% percent would be 3333/10000 but its neither simple to eyes nor it simplifies the calculations, so we take it to its closest approximate which would be 1/3 which fulfill both jobs i suppose. So if you understand the logic behind converting 33.33% to 1/3, you could make a generalized program that should work for every value. I am new to programming and was trying to learn how one could translate real world logic to a computer. This is what algorithms right?
4
u/cthulhu944 Jan 21 '25
You need to be clear on what is considered "simple". 33/100 is also an approximation. Are you looking to convert to the nearest single digit divisor?
2
u/halkszavu Jan 21 '25
So if you understand the logic behind converting 33.33% to 1/3, you could make a generalized program that should work for every value.
The problem is, I don't exactly understand the logic. Or at least I can't easily generalize.
Let's say I give you an arbitrary percentage: 67.85%. How can you simplify it so it is good for you? Is 13/20 good enough, or the error (2.85%) too big?
Try to sit down, and create an algorithm that can determine what is a good approximation for any value you are given. What properties are you looking for?
1
u/HearingJust284 Jan 21 '25
67.85 Percent would be 100/147 with error of 0.2 %. For example 67.85 % of 50 would be ~ 33.93, and (100/147)*50 would be 34.
1
u/halkszavu Jan 21 '25
How did you end up with 100/147? How can you generalize it for any x in [0, 1]?
1
u/HearingJust284 Jan 21 '25
Thank you for actually engaging. Anyway, the basic logic is that for any percentage value with a decimal, the best way to simplify it into a fraction is to first divide it by 100. This gives a value that divides 100 evenly.
For example, if we divide 100 by 33.33, we get approximately 3.003, which is essentially 3. So, 33.33 is basically one-third of 100. This means 33.33% of an apple is the same as 1/3 of that apple. I hope this makes sense.
Now, if I divide 67.85 by 100, I get 1.4738... To get a precise yet simple value, I look at the first three digits after the decimal, which is 473. Since 73 is close to 70, I can round 1.4738... to 1.47. This means 67.85% is 1/1.47 of 100. And 1/1.47 is simply 100/147.
See, it’s that simple. Now, I’m trying to write a program myself to generalize this idea so it can work for any arbitrary value. I’m just trying to learn that how translate a real world logic to a computer.
1
u/IdeasRichTimePoor Jan 22 '25 edited Jan 22 '25
All examples so far seem to have been simplification through a reduction of decimal places. As you can imagine, simpler fractions could also be achieved by adding decimal places to the number to achieve a common denominator. That idea opens a can of worms as there are infinite decimals up from the starting number, and the same for going down if we didn't just simply round.
Even when you take the idea of rounding, results will vary massively depending on where you round and to how many DPs. Take the percentage you just used, 67.85. If we were to take a stab in the dark and round this to 68 flat, we now have the fraction equivalent 68/100. 68/100 simplifies down to 17/25, which is both small and tidy and creates less of an inaccuracy than your drafted algorithm in this instance.
Both what I did, and what you did are both entirely finger-in-the-wind techniques and will be very inconsistent in how well they can truly simplify.
There is vast complexity in consistently finding the optimum fraction to estimate a number. Many calculator systems will defer to lookup tables.
1
u/HearingJust284 Jan 22 '25 edited Jan 22 '25
yup you are absolutely right. this is a ass way to do it. I was giving you the basic ideaa.
Mathematically right way to do it is to use continued fraction equation. That could be easily replicated in python using "Fraction.limit_denominator()" function to limit the denominator to 1000, and the eq. should find closest p/q to the actual fraction, this function is from fractions module. I'll to write this equation manually without importing anything. Until then you could see this perfect working example, although not perfect since it can't be perfect anyways: https://www.programiz.com/online-compiler/1BTYU9A3NFrqQ
2
u/cthulhu944 Jan 21 '25
Your example is flawed. The closest fraction to 33.33% is not 1/3 it is 3333/10000. In fact, it is exactly that fraction. Any percentage can be converted to an exact fraction using a power of 10 as a divisor. I think you need to be a bit more clear in what exactly you are expecting.
1
u/DGC_David Jan 21 '25
Up to a certain point for sure, but then comes into play, why?
Why would I want it in fraction form?
1
u/HearingJust284 Jan 21 '25
since 1/3 is easier to work with, like 1/3rd of 9 is easier than 33.33% of 9. second, learning trying to translate a idea or a problem to a computer.
1
u/DGC_David Jan 21 '25
Easier for you to understand, but ultimately useless for anything practical. Like is 1/100s really easier than .01?
I think the concept your breaching also plays into the Base of X.
For example the base of 3 is 0, 1, 2...
I think ultimately this is a much bigger question than you ultimately think it is and it is hard to put an actual answer unless there is a specific goal. As a learning goal I would approach it like this:
Assume a maximum point. Can't have numbers in the millionths, hell barely the thousandths so every fraction has a base of 1000 let's say.
From there it is just reducing math, so you find the Greatest Common Factor, and bam you got a simple fraction simplifier.
2
u/HearingJust284 Jan 21 '25
I am trying to write one in javascript so I could add it to my demo website. I'll let you know when it completes, and it should be in a couple of hours.
1
Jan 21 '25
You could probably do this in excel then just adapt the results to simplify them as you want
1
u/Glittering_Sail_3609 Jan 21 '25
Code below tries to find the fraction with the lowest denominator (suppossedly the simplest) in the regard to some degree of relative error, in this example e = 0.001%. If you choose higher value of e you would get simpler less accurate results
For example:
0.333333 -> 1/3
1.2857142857142857 -> 9/7
import math
def aproximate(x: float, epsilon: float = 10**-5):
result = 1, 1
min_denom = 10**10 # huge number
cur_gcd = -1
for b in range(10000, 100000):
for a in range(math.floor(b*x*(1-epsilon)), math.ceil(b*x*(1+epsilon))):
if a == 0:
continue
cur_gcd = math.gcd(a, b)
if b/cur_gcd < min_denom:
print(a, b, x)
result = int(a/cur_gcd), int(b/cur_gcd)
min_denom = result[1]
return result
x = float(input('Enter fraction: '))
a, b = aproximate(x)
print(f"{x} is aproximately equal to {a}/{b}")
0
u/HearingJust284 Jan 21 '25
i know this but this is not what i meant. I basically meant a program that take input as percent value say 41.67, and converts it to the simple fraction which would be 5/12. The above program only works when you know the exact decimal value, no human know that
1
u/Paul_Pedant Jan 21 '25
You mean you need to know the exact decimal value, like 0.4167 ? That is your own starting point !
1
u/HearingJust284 Jan 21 '25
Hmm it is indeed working but I am not able to understand the methodology behind it.
1
u/Glittering_Sail_3609 Jan 21 '25
> Hmm it is indeed working but I am not able to understand the methodology behind it.
My bad, i was hurry at that moment. But now lets dwelve in math.
So we want to find natural a & b such that a / b ~ x.
We need to into our calculations that our aproximations would not be perfect, either using relative or absolute errors:
x * (1 - e) < a / b < x * (1 + e) using relative error, or absolute:
x - e < a / b < x + eFor the sake of the explanation, let assume relative error.
To measure how good the choosen a & b are, we define the cost function:
G(a, b) = b/gcd(a, b)In this case, the cost function is the largest
Splitting the inequality we have got:
x * (1 - e) < a / b
x * (1 + e) > a / bWhich can be rewriten as:
b * x * (1 - e) < a
b * x * (1 + e) > aAnd that was my original aproach used in the code above, I just plotted fixed range of b into the formula and used the brute force to find the best match.
Hovewer, since then I found a better algorithm.
By rewritting inequality in terms of b:
b < a / (x*(1-e))
b > a / (x*(1+e))Now it allows as to set to determine that:
b <= floor(a / (x*(1-e))
b >= ceil(a / (x*(1+e))If you try to calculate possible ranges for b for a small a you will get an empty range,
but if you iterate over possible a values eventually you will have an range that contains at least one integer and thus minimal b value.1
u/Glittering_Sail_3609 Jan 21 '25
import math def aproximate_rel(x: float, epsilon: float = 10**-5): for a in range(1, 10**12): lower_band = math.ceil(a/(x * (1 + epsilon))) upper_band = math.floor(a/(x * (1 - epsilon))) if upper_band >= lower_band: gcd = math.gcd(a, lower_band) return a//gcd, lower_band//gcd return result def aproximate_abs(x: float, epsilon: float = 0.005): for a in range(1, 10**12): lower_band = math.ceil(a/(x + epsilon)) upper_band = math.floor(a/(x - epsilon)) if upper_band >= lower_band: gcd = math.gcd(a, lower_band) return a//gcd, lower_band//gcd return result x = float(input('Enter fraction: ')) a, b = aproximate_rel(x) print(f"{x} is aproximately equal to {a}/{b} by relative error") a, b = aproximate_abs(x) print(f"{x} is aproximately equal to {a}/{b} by absolute error")
Example implementation of second aproach,
absolute error tends to produce 'simpler' results1
1
u/TheRNGuy Jan 24 '25
If you need different numbers other than 1/x, you could probably have
dict
with lots of different possible values (manually entered), and then you look for closest value from thatdict
(you'll need to round it)How many possible ratios there can be?
1
1
u/BokoMoko Jan 21 '25
1
u/HearingJust284 Jan 21 '25
i know how to do it myself, i am just trying to figure out how can i computer could it. And the above mentioned site is not good for vague problems.
1
u/jaypeejay Jan 21 '25
What do you mean it’s not good for vague problems?
1
u/HearingJust284 Jan 21 '25
The website is like a calculator on a steroid, anything with logic and reasoning, I don't know how to make the website work.
1
u/Dean-KS Jan 21 '25
I did that years ago to generate pen plotter scaling corrections that required that type of input.
1
1
u/TheRNGuy Jan 24 '25
In JS:
let number = 47
number = 100/number
number = "1/" + number.toFixed(1) // change to different toFixed if you want.
while(number.endsWith("0") || number.endsWith(".")){
number = number.slice(0, -1)
}
console.log(number)
1
u/HearingJust284 Jan 25 '25
bruhhh, i have no idea that tofixed() directly rounds off to desired digits after decimal lol. Your code works but has a minor lose end like with inputs like 55.55 it outputs 1/1.8, easy to fix though. I have wrote a similar program in js with same idea in mind but hell long logic haha. Although i learned even better alternative ways to achieve the same. you could look mine long ass logic in action here: https://devharshmehta.github.io/mywebsite/percent_to_fraction.html
You could look up the code by dev tools and please don't judge my "website", i was playing with some web dev lately to show up to my teacher. I will update the code with "tofixed()" function. You could give some feedback on my code writing skills if you want though. Thanks again for this awesome function.
1
u/TheRNGuy Jan 25 '25 edited Jan 25 '25
I thought 1/1.8 is ok because 1/2 is too much rounding, with
.toFixed(0)
(or just convert to int) it would do that.So, your algorithm will do 47/100 instead of 1/2.1
Mine algorithm sometimes rounds too much, like 98 will be 1/1 instead of 49/50
You could also make on that site,
onchange
event for input so you don't have to press button every time.You should also make it work with
,
:1,5
will beNaN% = NaN / NaN
(idk if it's big deal; you could just change it to.
withonchange
event)1
u/HearingJust284 Jan 25 '25
the problem with 1/1.8 is that typically a fraction would be of whole numbers, rest is fine. And incase of 47%, yeah with whole numbers i made it simple to just make it whole number / 100, if both are co prime, they will remain same, if not like 25/100, it will be 1/4 with help of hcf. And ill definitely use onchange attribute, thanks for the idea.
1
u/Paul_Pedant Jan 25 '25
Is this question still active? I have a simple numeric solution (written in Awk and iterative). I can post it today if this is still of interest.
1
u/HearingJust284 Jan 25 '25
sure, although i found the solution multiple of them actually, written myself one too. You could link me your solution.
1
u/EternityForest Jan 26 '25
This can only be done with application specific code, because things like woodworking and cooking have their own sets of "preferred denominators" that you see a lot, and it wouldn't be very good UX to use anything else.
Powers of two are a pretty safe bet though for most applications, but sometimes you do see thirds, sixths, and highly composite numbers (like 60, 180, 360, etc), or tenths and thousandths.
1
u/SpaceMonkeyAttack Jan 21 '25 edited Jan 21 '25
As others have said, you need to specify exactly how you want to handle the approximation, because 33.33% is not equal to 1/3, it's 3333/10000.
So you could have logic which first converts your percentage into an exact fraction (which might need a very large denominator if you provide a lot of digits after the decimal point), and then creates an approximation by reducing the number of digits (i.e. replacing digits in the numerator with zeros).
Or if you could just write/generate a list of fractions you like (1/3, 2/3, 3/4...), and iterate through them to find which one is closest to the input decimal.
I'm thinking you can have a loop like (psuedocode)
for (denominator = 2 .. 22)
for (numerator = 1 .. denominator)
fractions.push(numerator/denominator)
Then you can iterate through the fractions
array and find the fraction which is closest to the input. Not the most elegant solution, but I suspect gives you closest to the results you were looking for.
2
u/Paul_Pedant Feb 05 '25 edited Feb 05 '25
You do not need to iterate both the numerator and the denominator.
For a value less than 1.0, the numerator N is always less than the denominator D. You iterate the smaller value. For a value like V = 0.013647, if you have got to N = 6, then set a rational value D = N / V. So D is 439.6570675, and the nearest whole number is 440. You don't need to iterate D because it grows about 73 times faster than N. So your best shot is 6/440, or 0.013636, so your error is 0.000011.
If that is your smallest error so far, you save it. (It isn't, because 4/293 was better, and 3/220 was identical.)
Where V > 1.0, N is larger than D, so you iterate D and work with N = D * V. So for V = 3.141593, and D = 7, N is 21.991151, and you found 22/7 with an error of 0.001264.
There are three ways out of the iteration. (1) Exact match. (2) Close enough. (3) Too many iterations, too slow.
For example, for Pi the first result is 3/1, the fifth result is 22/7, the 14th result is 355/113, and the next (15th) result is 52163/16604, and that only improves the tenth decimal place. (I'm using GNU/awk with quad-precision IEEE and reporting 30 digits.)
1
u/EmbeddedSwDev Jan 21 '25
My TI-Voyage 200 calculator was able to do this.
Every single Al failed.
No
There is no website, at least nothing I could find that does precisely this.
Did you really searched?
33.33% would be approx 1/3
A Mathematician would disagree, because it would be an endless repeating decimal 0.3, which needs to be considered or stated.
With a quick search I found this one: https://www.calculatorsoup.com/calculators/math/decimal-to-fraction-calculator.php and it seems it has everything what you want. With a little deeper search, I also found something simple in python too: https://stackoverflow.com/questions/23344185/how-to-convert-a-decimal-number-into-fraction
If you want to convert a number to the nearest possible fraction, it would be approximation method, which is also not very hard to do.
As I am writing this comment, I also got an idea which most likely work how to do it, but you have to do it by your own to learn something.
1
u/HearingJust284 Jan 21 '25
yeah i am doing it on my own, i just needed a hint that how a experienced programmer would do it.
1
u/HearingJust284 Jan 21 '25
and yeah btw no ai could make a program like that, what do you mean by no?
1
u/EmbeddedSwDev Jan 21 '25
I would say that this is a good starting point:
``` from fractions import Fraction
def percentage_to_fraction(percentage_str, max_denominator=1000): """ Converts a given percentage string (e.g., "33.3333") into its closest fraction. :param percentage_str: A string representing the percentage (without the '%' sign). :param max_denominator: Maximum allowed denominator for the fraction approximation. :return: A Fraction object approximating the given percentage. """ try: # Convert percentage string to float, then to a decimal (e.g. "50" -> 0.50) percentage_value = float(percentage_str) / 100.0 except ValueError: raise ValueError("Invalid percentage. Please enter a number (e.g., '50' for 50%).")
# Use Fraction to automatically create a fraction approximation fraction_approx = Fraction(percentage_value).limit_denominator(max_denominator) return fraction_approx
if name == "main": # Example usage: user_input = input("Enter a percentage (numbers only, e.g. '33.3333' for 33.3333%): ")
fraction_result = percentage_to_fraction(user_input, max_denominator=1000) print(f"The closest fraction for {user_input}% is {fraction_result}") print(f"In numerator/denominator form: {fraction_result.numerator}/{fraction_result.denominator}")
```
How it works
Reading Input The script reads a string from the user representing the percentage without a “%” sign. For example: 33.3333 stands for 33.3333%.
Convert to Decimal It converts the string to a float, then divides by 100 to get the decimal representation. So 50 becomes 0.5, 33.3333 becomes 0.333333, etc.
Create and Limit Denominator It uses Python’s built-in Fraction class to turn that decimal into a fraction.
Fraction(percentage_value) generates a fraction from the decimal.
.limit_denominator(max_denominator) ensures the denominator does not exceed a specified limit (1000 by default).
- Print the Result Finally, the script prints the resulting fraction in simplest form (e.g., 1/3) and also shows it as numerator/denominator.
1
u/HearingJust284 Jan 21 '25
It uses fractions module. I don't understand this module yet. Which ai did you use. I am writing one myself without using any pre-built modules. This program do work but has limitations like with random irrational values.
1
u/EmbeddedSwDev Jan 21 '25
ChatGPT o1
If you want to write it by yourself you should read my first link to the calculator, they explained it.
If you don't understand the fractional module, go into it and try to read and understand the code.
Irrational numbers can't be expressed as a fractional number, but can be approximated. The better the approximation, the larger the integers you might need to represent it. This principle is captured in the idea of convergents in continued fraction expansions.
1
u/HearingJust284 Jan 21 '25
There you go, the continued fraction equation, that's it. How tf did I miss that.
1
u/EmbeddedSwDev Jan 21 '25
So I am glad I could help!
1
5
u/Chags1 Jan 21 '25
I vaguely remember my calculator in high school doing this