1. ## Help With Algorithm

Hello,

I have an array of rational numbers, and I need to
find the smallest unit fraction derived from these numbers.

Below demonstrates what I want to do:
Code:
```   A R R A Y                fraction                            unit
---------------             in                                  fraction
decimal             lowest                   unit       as
index   number              terms      denominator   fraction   decimal
-----   -------             --------   -----------   --------   --------

[ 1 ]    0.1875               3/16         16          1/16      0.0625
[ 2 ]    0.375                3/8           8          1/8       0.125
[ 3 ]    0.5625               9/16         16          1/16      0.0625
[ 4 ]    0.75                 3/4           4          1/4       0.25
[ 5 ]    0.875                7/8           8          1/8       0.125```
From the above, the smallest unit fraction I am after is 0.0625

I'm scratching my head as how to start, and am hoping someone can get me going.

2. ## Re: Help With Algorithm

Maybe this code snippet can be of any use:
Code:
```' https://stackoverflow.com/questions/95727/how-to-convert-floats-to-human-readable-fractions
' Source: http://www.freevbcode.com/ShowCode.asp?ID=582
Public Function Dec2Frac(ByVal f As Double) As String
Dim df As Double
Dim lUpperPart As Long
Dim lLowerPart As Long

lUpperPart = 1
lLowerPart = 1

df = lUpperPart / lLowerPart
While (df <> f)
'While Abs(df - f) > 0.000001
If (df < f) Then
lUpperPart = lUpperPart + 1
Else
lLowerPart = lLowerPart + 1
lUpperPart = f * lLowerPart
End If
df = lUpperPart / lLowerPart
Wend
Dec2Frac = CStr(lUpperPart) & "/" & CStr(lLowerPart)
End Function```

3. ## Re: Help With Algorithm

OK thanks Arnoutdv

I will see if that helps.

4. ## Re: Help With Algorithm

mms_,

My first thought is that all rational numbers can't be represented as a non-repeating decimal. A trivial example is 1/3.

Are you wanting to further restrict your set-of-numbers to non-repeating rational numbers?

And, another issue that would take some thought is the issue of base-10 to base-2 (and vice-versa) conversion when using IEEE. I'm not sure if all non-repeating rational numbers can be represented perfectly in base-2 ... I'd have to think about that one. However, even if they can, you'll sometimes run into rounding issues because of the size of the mantissa (significand) in IEEE.

Even if you used the Decimal type, you'd still have to monitor mantissa underflows.

To do it generally, what you've proposed is a far from trivial problem.

Elroy

5. ## Re: Help With Algorithm

And just as another thought ... from a strictly definitional sense, all numbers stored in IEEE Single, IEEE Double, and/or Decimal types are rational. Also, from a strictly definitional sense, they're also non-repeating rational. You may say, "well, can't IEEE represent 1/3rd?" And, the answer is, "NOPE". It can approximate that repeating-rational-number with a very close non-repeating-rational-number, but it won't be exact.

And, regarding irrational numbers (pi, sqrt(2), etc), they're also just closely approximated with non-repeating-rational-numbers.

So, in terms of IEEE (or Decimal) storage, your question becomes somewhat different. Roughly, here's what you're asking:

"How do we find the prime numbers of the mantissa of a floating point number, and then factor them out of that mantissa, leaving a transformed prime number mantissa?" And, as such, that's not a horribly complex problem. Finding the prime numbers of a mantissa the size of IEEE Single, IEEE Double, or even Decimal isn't trivial, but it's far from impossible.

EDIT1: Actually, you're just asking for the largest prime number of the mantissa. And, to find the original fraction-numerator, just re-divide that mantissa-prime-number into the original number. This all ignores the sign bit, and also assumes we're dealing with numbers that are abs(n) < 1.

6. ## Re: Help With Algorithm

Elroy
my first answer is that my data will always be a result of denominators being a power of 2

In the mean-time I came up with the following, built upon Arnoutdv's Dec2Frac function
I had to modify it for my use.

It seems to work.
Any more comments/suggestions would still be appreciated.

Code:
```Option Explicit

Dim aRationalNumbers(1 To 5) As Double

Command1.Caption = "Solve"

' Load array with test numbers
aRationalNumbers(1) = 0.1875
aRationalNumbers(2) = 0.375
aRationalNumbers(3) = 0.5625
aRationalNumbers(4) = 0.75
aRationalNumbers(5) = 0.875

End Sub

Private Sub Command1_Click()

Dim numRationalNumbers As Long
numRationalNumbers = UBound(aRationalNumbers)

' Fill array of denominators
Dim i As Long
For i = 1 To UBound(aRationalNumbers)
Next i

' Print for inspection
For i = 1 To UBound(aDenominators)
Next i

' Walk through denominators array to find smallest
Dim lowestDec As Single
Dim thisDec As Single
lowestDec = 1
For i = 1 To UBound(aDenominators)
If thisDec < lowestDec Then lowestDec = thisDec
Next i

' Report solution
MsgBox "Smallest Unit Fraction (decimal) from aRationalNumbers() array = " & lowestDec

End Sub

Public Function Dec2FracDenom(ByVal f As Single) As Long

Dim df As Double
Dim lUpperPart As Long
Dim lLowerPart As Long

lUpperPart = 1
lLowerPart = 1

df = lUpperPart / lLowerPart

While (df <> f)
'While Abs(df - f) > 0.000001
If (df < f) Then
lUpperPart = lUpperPart + 1
Else
lLowerPart = lLowerPart + 1
lUpperPart = f * lLowerPart
End If
df = lUpperPart / lLowerPart
Wend

Dec2FracDenom = lLowerPart

End Function```

7. ## Re: Help With Algorithm

Ok, a denominator always a power-of-two does considerably simplify things. Those are even a further subset of non-repeating-rational-numbers.

8. ## Re: Help With Algorithm

Here's another question though, and something you didn't cover in your example.

Let's say we've got 2/16 as our original rational number (expressed as a ratio). What's the answer? Is it 1/16 or 1/8 (just simplified)?

9. ## Re: Help With Algorithm

2/16 is OK to be simplified as 1/8 and therefor resultant denominator is 8

10. ## Re: Help With Algorithm

All testing I've done seems to work with the exception of data sets containing whole numbers
Code:
```aRationalNumbers(1) = 2
aRationalNumbers(2) = 2
aRationalNumbers(3) = 4
aRationalNumbers(4) = 4
aRationalNumbers(5) = 2```
Technically these hold true to the denominator requirement being a powers of 2
(1 is technically a power of 2)
(ie 2/1 = 2, 4/1 = 4)

My code posted earlier yields a solution of 1 for the above data set, but I need it to be 2

Edit: Actually 1.5 could be valid data, so the problem is not only whole numbers,
but rather numbers greater than 1

11. ## Re: Help With Algorithm

Originally Posted by mms_
All testing I've done seems to work with the exception of data sets containing whole numbers
Code:
```aRationalNumbers(1) = 2
aRationalNumbers(2) = 2
aRationalNumbers(3) = 4
aRationalNumbers(4) = 4
aRationalNumbers(5) = 2```
Technically these hold true to the denominator requirement being a powers of 2
(1 is technically a power of 2)
(ie 2/1 = 2, 4/1 = 4)

My code posted earlier yields a solution of 1 for the above data set, but I need it to be 2

Edit: Actually 1.5 could be valid data, so the problem is not only whole numbers,
but rather numbers greater than 1
Why would you expect 2? i would expect 0 since 0 is the smallest fraction as per your requirement in Post 1

As for values greater than 1: Strip the integer part from it
Code:
```Public Function FractionPart(dblNumber As Double) As Double

FractionPart = (dblNumber - Fix(dblNumber))

End Function```
For whole numbers the expected result should be 1, since you come down with "WholeNumber/1" with your code.
Why don't you just check if it's a whole number (integer)?
The fun part starts if you have an array with mixed values.

EDIT 2: After thinking about it, it's even obvious, why you would get "1" for integers:
A "fraction" is always in the range of "0 < MyFraction <= 1", with MyFraction=1 meaning no fractional part at all (=Integer) and MyFraction never being zero
Yes, i know that you could turn the argument around with MyFraction=0 being an integer and MyFraction never being 1 but that's just me trying to stay sane mathematically.
To stay in your usecase: Instead of looking for the smallest unit-fraction, you could also look for the highest denominator, since your unit-fraction is always "1 / Denominator".
And with rising Denominator the actual value of the unit-fraction gets smaller and smaller but in that way can never reach zero.

12. ## Re: Help With Algorithm

Originally Posted by Zvoni
Why would you expect 2? ...
I would expect this is related to the Music based program that mms_ has been working on. The basic timing of notes is based on powers of 2 or sums of powers of 2.
And in the time signature, the bottom value which represents the note time value for the beat, (e.g. 2, 4, 8, etc) would not be 1, as far as I know. You can have quite a variety of time signatures, e.g. 3/4 or 2/2 or 6/8 or even 12/8, as just a few examples, but I've never seen anything over 1, e.g. 1/1 or 2/1 for timing.

So, I'm assuming that mms_ wants to limit the time signature choice to some value over 2 as the largest note value to be chosen. Note I said largest, and you might think that 2 is smaller than 4 so I misspoke, but in this case we're talking about musical note timing and those are represented as fractions of a whole. A whole is divided into half notes (2 = 1/2) or quarter notes (4 = 1/4), or eighth notes, sixteenth, 32nd or 64th.

I think the reason he mentions 1.5 is because you can have "dotted" notes, which extent the duration of a note by half its value, i.e. a dotted quarter note would be 3/8th long in duration 1/4 + (1/4)/2, or in other words 1.5 times its normal duration.

Of course you can have double dotted notes, so a double dotted quarter note would be 7/16ths in duration ( 1/4 + (1/4)/2 + (1/4)/4), which is 1.75 times its normal duration.

I'm not sure what particular aspect that mms_ is working on right now, but I'm sure it is related to musical timing in one way or another.

13. ## Re: Help With Algorithm

Ah, didn't know that.
his values reminded me of diameters for Bolts/screws/nuts in imperial units.
but musical notes definitely makes sense

EDIT: I'm a bloody idiot. This wouldn't let me rest, so i thought a bit more about it.
Your code returns the denominator, not the fraction, so it would be correct to say "0<= MyFraction <1".
A fraction is never 1, but can be zero meaning no fractional part.
*GROWL*

14. ## Re: Help With Algorithm

passel
You are good!

That is exactly what I am working on.
And it is when I came to dotted notes that this issue came up.

I have the notes playing correctly, but positioning them correctly on the page is proving to be somewhat complicated.
I think I have the positioning of standard notes, and dotted notes working properly, but now I am working on tuplets,
and that now is giving me some problems.

A single staff system is pretty easy, but when a system has multiple staffs (say Piano LH and Piano RH),
all notes in a measure, by convention, should be positioned correctly horizontally, so they visually communicate the correct timing.
And when a "playback bar" is running across the system, notes must be drawn in the correct position, so that
it hits each note at the exact time it is being played.

I hadn't mentioned the music aspect, as I was trying to keep the question as generic as possible, so as to solicit the most responses.

ps
1/1 and 2/1 are legit time signatures as far as I know

15. ## Re: Help With Algorithm

If it's a music thing, I'd definitely just create a lookup table for all the reasonable possibilities.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•