
Jan 14th, 2020, 12:57 PM
#1
Thread Starter
Hyperactive Member
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.

Jan 14th, 2020, 01:03 PM
#2
Re: Help With Algorithm
Maybe this code snippet can be of any use:
Code:
' https://stackoverflow.com/questions/95727/howtoconvertfloatstohumanreadablefractions
' 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

Jan 14th, 2020, 01:07 PM
#3
Thread Starter
Hyperactive Member
Re: Help With Algorithm
OK thanks Arnoutdv
I will see if that helps.

Jan 14th, 2020, 01:34 PM
#4
Re: Help With Algorithm
mms_,
My first thought is that all rational numbers can't be represented as a nonrepeating decimal. A trivial example is 1/3.
Are you wanting to further restrict your setofnumbers to nonrepeating rational numbers?
And, another issue that would take some thought is the issue of base10 to base2 (and viceversa) conversion when using IEEE. I'm not sure if all nonrepeating rational numbers can be represented perfectly in base2 ... 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
Last edited by Elroy; Jan 14th, 2020 at 01:50 PM.
Any software I post in these forums written by me is provided “AS IS” without warranty of any kind, expressed or implied, and permission is hereby granted, free of charge and without restriction, to any person obtaining a copy. Please understand that I’ve been programming since the mid1970s and still have some of that code. My contemporary VB6 project is approaching 1,000 modules. In addition, I have a “VB6 random code folder” that is overflowing. I’ve been at this long enough to truly not know with absolute certainty from whence every single line of my code has come, with much of it coming from programmers under my employ who signed intellectual property transfers. I have not deliberately attempted to remove any licenses and/or attributions from any software. If someone finds that I have inadvertently done so, I sincerely apologize, and, upon notice and reasonable proof, will reattach those licenses and/or attributions. To all, peace and happiness.

Jan 14th, 2020, 01:50 PM
#5
Re: Help With Algorithm
Further reply:
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 nonrepeating rational. You may say, "well, can't IEEE represent 1/3rd?" And, the answer is, "NOPE". It can approximate that repeatingrationalnumber with a very close nonrepeatingrationalnumber, but it won't be exact.
And, regarding irrational numbers (pi, sqrt(2), etc), they're also just closely approximated with nonrepeatingrationalnumbers.
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 fractionnumerator, just redivide that mantissaprimenumber into the original number. This all ignores the sign bit, and also assumes we're dealing with numbers that are abs(n) < 1.
Last edited by Elroy; Jan 14th, 2020 at 02:04 PM.
Any software I post in these forums written by me is provided “AS IS” without warranty of any kind, expressed or implied, and permission is hereby granted, free of charge and without restriction, to any person obtaining a copy. Please understand that I’ve been programming since the mid1970s and still have some of that code. My contemporary VB6 project is approaching 1,000 modules. In addition, I have a “VB6 random code folder” that is overflowing. I’ve been at this long enough to truly not know with absolute certainty from whence every single line of my code has come, with much of it coming from programmers under my employ who signed intellectual property transfers. I have not deliberately attempted to remove any licenses and/or attributions from any software. If someone finds that I have inadvertently done so, I sincerely apologize, and, upon notice and reasonable proof, will reattach those licenses and/or attributions. To all, peace and happiness.

Jan 14th, 2020, 01:54 PM
#6
Thread Starter
Hyperactive Member
Re: Help With Algorithm
Elroy
With regards to your question about nonrepeating decimals,
my first answer is that my data will always be a result of denominators being a power of 2
I will have to think about this more to confirm that however.
In the meantime 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
Private Sub Form_Load()
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)
Dim aDenominators() As Long
ReDim aDenominators(1 To numRationalNumbers)
' Fill array of denominators
Dim i As Long
For i = 1 To UBound(aRationalNumbers)
aDenominators(i) = Dec2FracDenom(aRationalNumbers(i))
Next i
' Print for inspection
For i = 1 To UBound(aDenominators)
Debug.Print aDenominators(i)
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)
thisDec = 1 / aDenominators(i)
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
Last edited by mms_; Jan 14th, 2020 at 01:58 PM.

Jan 14th, 2020, 02:06 PM
#7
Re: Help With Algorithm
Ok, a denominator always a poweroftwo does considerably simplify things. Those are even a further subset of nonrepeatingrationalnumbers.
Any software I post in these forums written by me is provided “AS IS” without warranty of any kind, expressed or implied, and permission is hereby granted, free of charge and without restriction, to any person obtaining a copy. Please understand that I’ve been programming since the mid1970s and still have some of that code. My contemporary VB6 project is approaching 1,000 modules. In addition, I have a “VB6 random code folder” that is overflowing. I’ve been at this long enough to truly not know with absolute certainty from whence every single line of my code has come, with much of it coming from programmers under my employ who signed intellectual property transfers. I have not deliberately attempted to remove any licenses and/or attributions from any software. If someone finds that I have inadvertently done so, I sincerely apologize, and, upon notice and reasonable proof, will reattach those licenses and/or attributions. To all, peace and happiness.

Jan 14th, 2020, 02:08 PM
#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)?
Any software I post in these forums written by me is provided “AS IS” without warranty of any kind, expressed or implied, and permission is hereby granted, free of charge and without restriction, to any person obtaining a copy. Please understand that I’ve been programming since the mid1970s and still have some of that code. My contemporary VB6 project is approaching 1,000 modules. In addition, I have a “VB6 random code folder” that is overflowing. I’ve been at this long enough to truly not know with absolute certainty from whence every single line of my code has come, with much of it coming from programmers under my employ who signed intellectual property transfers. I have not deliberately attempted to remove any licenses and/or attributions from any software. If someone finds that I have inadvertently done so, I sincerely apologize, and, upon notice and reasonable proof, will reattach those licenses and/or attributions. To all, peace and happiness.

Jan 14th, 2020, 02:17 PM
#9
Thread Starter
Hyperactive Member
Re: Help With Algorithm
2/16 is OK to be simplified as 1/8 and therefor resultant denominator is 8

Jan 14th, 2020, 04:09 PM
#10
Thread Starter
Hyperactive Member
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
Last edited by mms_; Jan 14th, 2020 at 04:18 PM.

Jan 15th, 2020, 06:42 AM
#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
EDIT: Sorry, i misread.
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 unitfraction, you could also look for the highest denominator, since your unitfraction is always "1 / Denominator".
And with rising Denominator the actual value of the unitfraction gets smaller and smaller but in that way can never reach zero.
Last edited by Zvoni; Jan 15th, 2020 at 09:48 AM.
One System to rule them all, One IDE to find them,
One Code to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie

People call me crazy because i'm jumping out of perfectly fine airplanes.

For health reasons i try to avoid reading unformatted Code

Jan 15th, 2020, 10:50 AM
#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.
"Anyone can do any amount of work, provided it isn't the work he is supposed to be doing at that moment" Robert Benchley, 1930

Jan 15th, 2020, 11:13 AM
#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*
Last edited by Zvoni; Jan 15th, 2020 at 12:32 PM.
One System to rule them all, One IDE to find them,
One Code to bring them all, and to the Framework bind them,
in the Land of Redmond, where the Windows lie

People call me crazy because i'm jumping out of perfectly fine airplanes.

For health reasons i try to avoid reading unformatted Code

Jan 15th, 2020, 12:56 PM
#14
Thread Starter
Hyperactive Member
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
Last edited by mms_; Jan 15th, 2020 at 01:35 PM.

Jan 15th, 2020, 01:22 PM
#15
Re: Help With Algorithm
If it's a music thing, I'd definitely just create a lookup table for all the reasonable possibilities.
Any software I post in these forums written by me is provided “AS IS” without warranty of any kind, expressed or implied, and permission is hereby granted, free of charge and without restriction, to any person obtaining a copy. Please understand that I’ve been programming since the mid1970s and still have some of that code. My contemporary VB6 project is approaching 1,000 modules. In addition, I have a “VB6 random code folder” that is overflowing. I’ve been at this long enough to truly not know with absolute certainty from whence every single line of my code has come, with much of it coming from programmers under my employ who signed intellectual property transfers. I have not deliberately attempted to remove any licenses and/or attributions from any software. If someone finds that I have inadvertently done so, I sincerely apologize, and, upon notice and reasonable proof, will reattach those licenses and/or attributions. To all, peace and happiness.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
