-1

What algorithm can I use to describe a specified gradient (N/M) approximately as the sum of a set of rational fractions { (n1/m1) + (n2/m2) … } ?

Design constraints:

  • The algorithm takes as input (N, M), describing the true gradient N/M.

    • N and M are integers.
    • If it matters: M is typically around 100–1000.
    • If it matters: N ranges widely, from low (1, shallow gradient) all the way to arbitrarily large (quintillions, extremely steep gradient approaching vertical).
  • The algorithm produces as output some small set of tuples, { (n1, m1), (n2, m2), …}.

    • The combination of tuples (n, m) will, when combined as fractions, closely approximate the gradient N/M.
    • The number of tuples should be small (I would expect fewer than 3).
    • Every n and m is an integer.
    • Every m is as small as can be, but no smaller than the minimum for M (e.g. 100).

Example

  • Given the input (50001, 1000)

    • the algorithm may generate the set { (5000, 100), (1, 1000) }
    • because (50001 / 1000) == ((5000/100) + (1/1000)).
    • The output is good because it's a small set, and the denominators are low while still being above the minimum.
  • Given the input (14, 1000)

    • the algorithm may generate the set { (1, 100), (1, 250) }
    • because (14/1000) == (1/100) + (1/250).
    • The output is good because it's a small set, and the denominators are low while still being above the minimum.
  • Given the input (5.07e+30, 1000)

    • the algorithm may generate the set { (5.07e+29, 100) }
    • because (5.07e+30/1000) == (5.07e+29/100).
    • The output is good because it's a small set, and the denominators are low while still being above the minimum.

I don't know for sure those are the best outputs; but they would satisfy the criteria.

Math formulae appreciated but I am not math-literate

My algebra is not strong enough to describe this generally. Likewise, I am not able to look at a description in mathematical language and know what algorithm it describes; nor am I able to tell whether it actually answers this question.

Thank you for references like

etc., but I can't translate that into pseudo-code for an algorithm. Please suggest some pseudo-code in an answer, so I can figure out whether it's doing what I described.

  • 1
    I don't understand your requirements. In your first example, why is your suggested solution better than simply returning (50001, 1000) by itself? What are you doing with the outputs? – Jules Jan 9 '18 at 7:24
  • You need more criteria to define an algorithm. Notions like "typically fewer than 3", "M is typically around 100-1000", and "closely approximate the gradient" are pretty fuzzy. You also need to provide an example breakdown with N in the quintillions. – Erik Eidt Jan 9 '18 at 7:24
  • Take your example 14/1000. You essentially split 14 into 10 and 4, and then reduce them to their common denominators. I understand the second part, but I don't see why it wouldn't return say (7, 500). Is it split because 500 is larger than 250 or 100? It seems to me like the trick here is that you bite off chunks such that you get numbers that are multipliers of as many prime numbers as possible (hence divisible by many numbers). – Neil Jan 9 '18 at 7:54
  • 2
    Maybe you could explain the purpose of the algorithm, so we don't have an X/Y Problem here. – doubleYou Jan 9 '18 at 13:17
  • These requirements allow many different outputs for any particular input. That may be fine with you but it leaves us feeling like you forgot state all of your requirements. – candied_orange Jan 9 '18 at 14:32
-1

This is the current algorithm I have; it is somewhat overwrought, because I'm trying to express the parts so I can understand how the result is formed.

Given `step_max` is 1000
Given `step_min` is 100

Function `describe_gradient_as_fractions` with inputs `N`, `M`

    Let `fractions` be an empty set

    If `N` <= 0:
        Return `fractions`

    Let `step_min_per_max` be (`step_max` / `step_min`)

    Let `n` be the integer part of (`N` / `step_min_per_max`)
    Let `m` be `step_min`
    If `n` > 0:
        Add a tuple (`n`, `m`) to `fractions`

    Let `n_remain` be (`N` − (`n` * `step_min_per_max`))
    Let `step_remain` be the integer part of (`m_max` / `m_remain`)
    Let `n` be the ceiling of (`n_remain` / (`m_max` / `step_remain`))
    Let `m` be `step_remain`
    If `n` > 0:
        Add a tuple (`n`, `m`) to `fractions`

    Return `fractions`
-1

Despite it not being entirely clear what the requirements are, I think I might have a nice answer.

Start by splitting M into its prime factors. For example if M = 5100, you can write M as 2^2 * 3 * 5^2 * 17.

Take the largest of these prime factors that is smaller or equal to N and call this q. Then, you can rewrite N as a * q + b. a can be found by dividing N by q and rounding down. b is the remainder.

Using the same example, if N = 53, then q would be 5^2 = 25. N can be rewritten as 2 * 25 + 3.

Next, split up the fraction as follows.

N/M = a*q/M + b/M

Since q divides M, the fraction becomes

N/M = a/M' + b/M

The result of the example would be

53/5100 = 2/204 + 3/5100

You can repeat this process a couple of times on the remaining b/M. The end result would be

53/5100 = 2/204 + 1/1700

(If you want to have the fewest splits possible, you should try to find the largest combination of prime factors smaller or equal to N and use that result as q.)

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.