Take the 2-minute tour ×

Suppose I have an array of non-repeating decimal numbers:

v1 = 0.0588235294117647, 0.1428571428571429, 0.0526315789473684, 0.0769230769230769

I would like to convert this to an array of integers by multiplying/dividing all the elements by a single number:

v2 = 1729, 4199, 1547, 2261

All numbers need to be in their most simple form as well. To clarify, this is the solutions column of a matrix with one free variable. I need to make that variable equal something that makes the entire column consist of whole integers.

I've tried a bunch of things, but nothing seems to work all the time.

I need some type of algorithm so that I can automate this process.

share|improve this question
I see no relationship between these values. Where did you get them? How did you arrive at those integers? –  duffymo Dec 24 '11 at 2:33
It's unclear what you want the relationship between v1 and v2 to be. –  Greg Hewgill Dec 24 '11 at 2:33
v1 and v2 are simply examples to demonstrate what I meant by "non-repeating decimal vector" and "whole integer vector" respectively. I just made them up for this post. Sorry about that. –  George Costanza Dec 24 '11 at 2:34
Why not multiply each number by 10 until they all become integral? –  mtrw Dec 24 '11 at 2:34
You could multiply v1 * 0, that's whole. –  Greg Hewgill Dec 24 '11 at 2:36
show 1 more comment

closed as not a real question by Paulpro, Mitch Wheat, woodchips, duffymo, ChrisF Dec 24 '11 at 15:09


2 Answers

Based on your comment on the other answer, your question seems to be how to scale a vector up so that all the values are integral.

This is not an easy task as you essentially need to find fractional approximations for all the numbers in v1.

Related: Algorithm for finding the ratio of two floating-point numbers?

There are essentially 2 main approaches to do this depending on what kind of numbers you want:

1) The easy way: You could multiply the vector by 2 until everything becomes integral. This is guaranteed to happen since all current systems use binary floating-point. This is essentially the first answer in the above question.

There is one major drawback to this approach. If your numbers are like:


you will get very "weird" (and potentially large) results. (you will not get: 20, 6, 15 which is the desired answer)

2) The hard way: This approach is to use continued fractions on each element of v1 to turn it into an array of fractions. Then multiply every element by the LCM of all the denominators. This is essentially the second answer in the above question.

The drawback of this approach is that it's math intensive and complicated. So you're better off just copying the implementation in that answer. The advantage is that it will give better results.

share|improve this answer
Thank you. This is what I wanted. –  George Costanza Dec 25 '11 at 1:32
If this answers your question, you can accept it by clicking on the green checkmark. :) –  Mysticial Dec 25 '11 at 1:55
add comment

If I understand you correctly you want to do something that ay result in very very large integers.

You want to find an integer (preferably smallest possible, but that may not be fast to find) that is a multiple of 3.3837475943, call it m1. Then do the same so you have m1, m2, m3, m4. Then you want to find their lowest common multiple lcm(m1, m2, m3, m4) or just use m1*m2*m3*m4 to avoid compute lcm. And multiply your vector v1, by the result. This will result in enormous integers in your vector (which will almost always not be able to be stored in 64 bits).

So say for your above numbers you could easily pick:

m1 = 33837475943
m2 = 89391713934747847847
m3 = 23282781272732734
m4 = 32838723
m = m1*m2*m3*m4 //2312684250534946337531905217893260302519969924182717722
v2 = m*v1

You may want to use the Fast Fourier Transform to multiply your m's since they are quite large you can have O(n log(n)) multiplication instead of , but I don't know if these numbers are large enough for it to really be beneficial.

share|improve this answer
Basically, right. Then I want to reduce it to its "simplest" form, which would require dividing uniformly by some number. –  George Costanza Dec 24 '11 at 3:01
@GeorgeCostanza If you pick the smallest multiple (rather than just multiplying by a power of 10 for each number, and use the lowest common multiple of the result instead of m1*m2*m3*m4 you will have the result. Otherwise you could do it the above way and then find the greatest common divisor of the numbers in your v2 and divide them all by that. –  Paulpro Dec 24 '11 at 3:05
@GeorgeCostanza I reccomend that second way actually. You can use this gcd(a,b) = gcd(b,a mod b) with a > b to find the gcd of two numbers quite fast. You need to find the gcd of n (say 4 like in your example) large numbers, then use gcd(v[1], gcd(v[2], gcd(v[3], v[4])))` –  Paulpro Dec 24 '11 at 3:07
add comment
