Results 1 to 15 of 15

Thread: Help With Algorithm

  1. #1

    Thread Starter
    Hyperactive Member
    Join Date
    Nov 2018
    Posts
    263

    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. #2
    PowerPoster Arnoutdv's Avatar
    Join Date
    Oct 2013
    Posts
    3,858

    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. #3

    Thread Starter
    Hyperactive Member
    Join Date
    Nov 2018
    Posts
    263

    Re: Help With Algorithm

    OK thanks Arnoutdv

    I will see if that helps.

  4. #4
    PowerPoster Elroy's Avatar
    Join Date
    Jun 2014
    Location
    Near Nashville TN
    Posts
    6,316

    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
    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 mid-1970s 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 re-attach those licenses and/or attributions. To all, peace and happiness.

  5. #5
    PowerPoster Elroy's Avatar
    Join Date
    Jun 2014
    Location
    Near Nashville TN
    Posts
    6,316

    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 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.
    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 mid-1970s 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 re-attach those licenses and/or attributions. To all, peace and happiness.

  6. #6

    Thread Starter
    Hyperactive Member
    Join Date
    Nov 2018
    Posts
    263

    Re: Help With Algorithm

    Elroy
    With regards to your question about non-repeating 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 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
    
    
    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.

  7. #7
    PowerPoster Elroy's Avatar
    Join Date
    Jun 2014
    Location
    Near Nashville TN
    Posts
    6,316

    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.
    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 mid-1970s 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 re-attach those licenses and/or attributions. To all, peace and happiness.

  8. #8
    PowerPoster Elroy's Avatar
    Join Date
    Jun 2014
    Location
    Near Nashville TN
    Posts
    6,316

    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 mid-1970s 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 re-attach those licenses and/or attributions. To all, peace and happiness.

  9. #9

    Thread Starter
    Hyperactive Member
    Join Date
    Nov 2018
    Posts
    263

    Re: Help With Algorithm

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

  10. #10

    Thread Starter
    Hyperactive Member
    Join Date
    Nov 2018
    Posts
    263

    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.

  11. #11
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    2,203

    Re: Help With Algorithm

    Quote Originally Posted by mms_ View Post
    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 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.
    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

  12. #12
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,047

    Re: Help With Algorithm

    Quote Originally Posted by Zvoni View Post
    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

  13. #13
    PowerPoster Zvoni's Avatar
    Join Date
    Sep 2012
    Location
    To the moon and then left
    Posts
    2,203

    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

  14. #14

    Thread Starter
    Hyperactive Member
    Join Date
    Nov 2018
    Posts
    263

    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.

  15. #15
    PowerPoster Elroy's Avatar
    Join Date
    Jun 2014
    Location
    Near Nashville TN
    Posts
    6,316

    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 mid-1970s 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 re-attach 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
  •  



Click Here to Expand Forum to Full Width