I am looking for the smallest numbers $m_a'$ and $m_b'$ so that they have n decimals and following expressions still hold: \begin{equation} \begin{cases} \frac{m_a'}{m_b'}=\frac{C_a}{C_b} \\ m_a'\geq m_a\\ m_b' \geq m_b \end{cases} \end{equation}

I know this is possible with a for loop, but since computation time is very important I wonder if there is a mathematical solution for this problem (using for example $ceil$ and $floor$ functions)? I have tried to solve this by rewriting $m_a'$ and $m_b'$ as follow: \begin{equation} \begin{cases} m_a'=l_a*n_d\\ m_b'=l_b*n_d\\ \end{cases} \end{equation} Where $l_a$ and $l_b$ are two integers and $n_d$ the number of decimals which are required (ex. $n_d=0.01$ for 2 decimals). Then I use this together with the two inequalities: \begin{equation} \begin{cases} \frac{m_a'}{m_b'}=\frac{C_a}{C_b}=\frac{m_a}{m_b}\frac{k}{k} \\ k*l_a \geq \frac{m_a}{n_d} \\ k*l_b \geq \frac{m_b}{n_d} \\ \end{cases} \end{equation}

At this stage I should search for the smallest $l_a$ and $l_b$ satisfying conditions above, but I do not know how to proceed at this point.


The first equality means that $\frac{C_a}{C_b}$ is rational thus we can write it as $\frac{p}{q}$ with p,q coprime integers. you can replace $m_{a'}$ by $m_{b'}$ on the first equality: $m_{a'}= \frac{p}{q}m_{b'}$ and then we replace it in the inequality: $\frac{p}{q}m_{b'} \geq m_a$ and thus $m_{b'} \geq max(\frac{q}{p}m_a, m_b)$ and since $m_{b'}$ has to be an integer we need to ceiling that number and since $m_{a'}$ has to be an integer $m_{b'}$ has to be divisble by q: $m_{b'} = q \cdot \text{ceil}(\text{ceil}(\text{max}(\frac{q}{p}m_a, m_b))/q)$

from math import ceil
from fractions import Fraction

def smallest_inst(CaCb, ma, mb):
    frac = Fraction(CaCb).limit_denominator(1000)
    p = frac.numerator
    q = frac.denominator
    mb_res = q*ceil(ceil(max(q/p *ma, mb))/q)
    ma_res = int(mb_res*p/q)
    assert abs(ma_res/mb_res - CaCb) < 1e-10
    assert ma_res >= ma
    assert mb_res >= mb
    return ma_res, mb_res

CaCb = 3.1415929203539825 # Ca/Cb
print(smallest_inst(CaCb, ma, mb))
(4260, 1356)

Finding p and q is the bottleneck. Which is a greatest common divisor kind of problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.