[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 436
  • Last Modified:

lil Math Help Modulus Maybe?

ok I have numbers from 0 to 65536   I need to find out what 2 numbers multiply together to equal that number
Z = 4556 as an example

so X * Y = Z
X and Y also can only be from 1 to 255

as such 256*256 = 65535

Ive heard someone mention using modulus but im not sure what the formula would look like

0
o0JoeCool0o
Asked:
o0JoeCool0o
  • 11
  • 7
  • 6
  • +3
3 Solutions
 
Shiju SasidharanCommented:
hi
'try this
'Place a
'           Command button
'           Text box
' and a
'           ListBox
' to ur form and use this code
'=================================

Private Sub Form_Load()
    Command1.Caption = "Get Factors"
    Text1.Text = "4556"
End Sub

Private Function ListFactors(ByVal ProductNum As Long)
On Error GoTo Last
Dim i, j
    List1.Clear
    For i = 1 To 255
        For j = 1 To 255
            If i * j = ProductNum Then
                List1.AddItem i & " X " & j & " = " & ProductNum
                Exit For
            End If
            If i * j > ProductNum Then Exit For
        DoEvents
        Next j
    Next i
    MsgBox List1.ListCount & " Entries Found"
   
Last:
If Err.Number <> 0 Then
    MsgBox Err.Description
    Err.Clear
End If
End Function

Private Sub Command1_Click()
    Call ListFactors(Text1.Text)
End Sub
'=================================

;-)
Shiju
0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
Private Sub Command1_Click()
    Dim result As Long
    result = 5148
   
    Dim x As Long
    Dim y As Long
   
    Debug.Print "result = " & result
    For x = 1 To 255
        If result Mod x = 0 Then
            y = result / x
            Debug.Print x & " * " & y & " = " & (x * y)
        End If
    Next x
End Sub
0
 
S-TwilleyCommented:
thought I'd diverge from my usual haunt and a see a familar face!

Depend's how complicated you want to get... since you're working with a relatively small set of numbers... a simple loop  should do.

If you want to get more complicated... you can look at the last digit (least significant or units digit) of your number Z and think about what two numbers when multiplied can give that number... you can use this to eliminate some of your options.

Another alternative is to calculate the prime numbers up to 256 (or just have them programmed in since its a smallish set)... then test whether your number Z is divisible by the prime numbers... if so, that prime number (or a multiple of it) is one of your factor pairs. The basis for this being that all numbers are a product of primes (except the primes themselves which as you know are a just a product of themselves and 1).

Just thought I'd add my comment to this (been working on a similar program recently after seeing a newspaper article on the newly discovered prime number)

http://www.guardian.co.uk/g2/story/0,,1430206,00.html#article_continue
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
Shiju SasidharanCommented:
hi
      ok Idle_Mind , Nice way of calculation

but , o0JoeCool0o  wants the operands to be between 1 and 255
 >> X and Y also can only be from 1 to 255

;-)
Shiju

0
 
S-TwilleyCommented:
As far as i can tell... Idle's should do that as well...

x starts off low and works up to 255... and if you like, y starts at 65535 and works down and they meet somewhere in the middle... that's not exactly what's happening, but they all pair off correctly
0
 
S-TwilleyCommented:
when x = :

1: y = result / x = 5148
2: y =        "     = 2574
...
...

===========

one lil comment is that the loop only needs to go up to the square root of the target
0
 
S-TwilleyCommented:
It'd be interesting to test the efficiency of different algorithms... but obviously can't do this on seperate machines... and you'd want to test on smaller and larger numbers
0
 
JigglyDCommented:
Okay... quick calculation and display...

You will want to use the built in SQR() function; as I did in the following form code.

__________________________________________
Option Explicit

Private Sub Text1_Change()
  Dim Multiplier(2) As Double
 
  If IsNumeric(Text1.Text) Then
     Multiplier(0) = Int(Sqr(CDbl(Text1.Text)))
     Multiplier(1) = Int(CDbl(Text1.Text) / Multiplier(0))
     Multiplier(2) = CDbl(Text1.Text) - (Multiplier(0) * Multiplier(1))
     Label1.Caption = " = " & Multiplier(0) & " * " & Multiplier(1)
     If Multiplier(2) <> 0 Then
        Label1.Caption = Label1.Caption & " (with a remainder of " & Multiplier(2) & ")"
     End If
  End If
End Sub
__________________________________________

Jiggle On ! ! !
0
 
pegasysCommented:
Private Sub Command1_Click()
    Dim result As Long
    result = 5148
   
    Dim x As Long
    Dim y As Long
   
    Debug.Print "result = " & result
    For x = 1 To 255
        If (result Mod x = 0) and  (y=>1) and (y<=255) Then
            y = result / x
            Debug.Print x & " * " & y & " = " & (x * y)
        End If
    Next x
End Sub
0
 
Shiju SasidharanCommented:
hi what about this
quite fast ?
'==========================
Private Sub Command1_Click()
Dim i As Long
Dim j As Long
Dim ProductNum As Long
    List1.Clear
    ProductNum = CLng(Text1.Text)
    If ProductNum = 0 Then Exit Sub
    For i = 255 To 1 Step -1
        If ProductNum Mod i = 0 Then
            x = ProductNum / i
            If x > 255 Then GoTo Nxt
            List1.AddItem x & " X " & i & " = " & ProductNum
            List1.AddItem i & " X " & x & " = " & ProductNum
            i = IIf(i / 2 > x, i / 2 + 1, x - 1)
        End If
        If i < x Then Exit For
Nxt:
   Next i
End Sub
'==========================
;-)
Shiju
0
 
pegasysCommented:
Private Sub Command1_Click()
    Dim result As Long
    result = 5148
   
    Dim x As Long
    Dim y As Long
   
    Debug.Print "result = " & result
    For x = 1 To 255
        For y = 1 to 255
        Next y
        If (x * y = result) Then
            Debug.Print x & " * " & y & " = " & result
        End If
    Next x
End Sub
0
 
Shiju SasidharanCommented:
oops , ignore my last post thats not correct
0
 
S-TwilleyCommented:
you can filter out your for loops  with a Step 2  if the target is odd... since it's not possible to have an even factor (when you're just talking about X * Y)...

0
 
Shiju SasidharanCommented:
'What about Recursion guys ?
' just check it out its really fast.
'======================================
Private Sub Command6_Click()
    List1.Clear
    Call ListFactors(Text1.Text, 1, 255)
End Sub
Private Function ListFactors(ProductNum As Long, low As Integer, high As Integer)
    Dim x
    While low < high
        If ProductNum Mod low = 0 Then
            x = ProductNum / low
            If x < 256 Then
                List1.AddItem x & " X " & low
                List1.AddItem low & " X " & x
                If x < high And x > low Then high = x
            End If
        End If
        low = low + 1
        high = high - 1
        Call ListFactors(ProductNum, low, high)
    Wend
End Function
'=======================================
;-)
Shiju
0
 
Shiju SasidharanCommented:
please change this
>>Private Sub Command6_Click()
by

Private Sub Command1_Click()

0
 
S-TwilleyCommented:
We really need some way of seeing which algorithm is most effective.... well we don't need to, but would be nice to know... obviously testing your own algorithm on your own machine and testing against someone else's by comparing time taken won't work because of the speed of the machines differ... so really need to test each person's algorithm on your own machine, and post up the time taken... but test over a wide range (possibly all test cases from 0 to 65536... or from 5000 to 7000... or something at least)....

I mean i'm interested in knowing the most efficient...

if this is the case, need to keep some regularity between the algorithm's... like we don't need to display the data, but just tally up the total number of pairs..

if you're interested, suggest your ideas on comparing
0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
How about this then?

Private Sub Command1_Click()
    Dim result As Long
    Dim x As Long
    Dim y As Long
    Dim f(255) As Boolean
   
    result = 1000
    Debug.Print "result = " & result
   
    For x = 1 To 255
        If Not f(x) Then
            If (result Mod x) = 0 Then
                y = CLng(result / x)
                If y <= 255 Then
                    If Not f(y) Then
                        f(x) = True
                        f(y) = True
                        Debug.Print x & " * " & y & " = " & result
                    Else
                        Exit Sub
                    End If
                End If
            End If
        End If
    Next x
End Sub

0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
shijusn,

Your second submission produces incorrect results.

For example, with a product of 1000, it misses 5 * 200 = 1000 and 10 * 100 = 1000

I will do some time trials with the other various methods submitted and post the results.

~IM
0
 
o0JoeCool0oAuthor Commented:
WOW what a response! lol Im going to try a fe w of these and see wich has the best performance gain this will be used in writing to file for IO processing. I will report back with the fastest method and credit the points

Thanks guys outstanding!
0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
Here is a simple test app that tests the three basic approaches submitted.

The results were:

    Idle_Mind: 0.8496094 secs
    shijusn: 1.101563 secs
    pegasys: 94.9375 secs


' ------------------------------------
' Test App
' ------------------------------------
Option Explicit

Private Sub Command1_Click()
    Command1.Enabled = False

    Dim r As Long
    Dim startTime As Single
    Dim endTime As Single
   
    startTime = Timer
    For r = 1 To 10000
        Call Idle_Mind(r)
    Next r
    endTime = Timer
    Label1.Caption = "Idle_Mind(): " & endTime - startTime
    Label1.Refresh
   
    startTime = Timer
    For r = 1 To 10000
        Call shijusn(r)
    Next r
    endTime = Timer
    Label2.Caption = "shijusn(): " & endTime - startTime
    Label2.Refresh
   
    startTime = Timer
    For r = 1 To 10000
        Call pegasys(r)
    Next r
    endTime = Timer
    Label3.Caption = "pegasys(): " & endTime - startTime
    Label3.Refresh
   
    Command1.Enabled = True
End Sub


Private Sub Idle_Mind(ByVal result As Long)
    Dim x As Long
    Dim y As Long
    Dim f(255) As Boolean
   
    'Debug.Print "result = " & result
    For x = 1 To 255
        If Not f(x) Then
            If (result Mod x) = 0 Then
                y = CLng(result / x)
                If y <= 255 Then
                    If Not f(y) Then
                        f(x) = True
                        f(y) = True
                        'Debug.Print x & " * " & y & " = " & result
                    Else
                        Exit Sub
                    End If
                End If
            End If
        End If
    Next x
End Sub

Private Sub shijusn(ByVal ProductNum As Long)
    'Debug.Print "ListFactors(" & ProductNum & ")"
    Call ListFactors(ProductNum, 1, 255)
End Sub

Private Function ListFactors(ProductNum As Long, low As Integer, high As Integer)
    Dim x
    While low < high
        If ProductNum Mod low = 0 Then
            x = ProductNum / low
            If x < 256 Then
                'Debug.Print x & " X " & low & " = " & ProductNum
                If x < high And x > low Then high = x
            End If
        End If
        low = low + 1
        high = high - 1
        Call ListFactors(ProductNum, low, high)
    Wend
End Function

Private Sub pegasys(ByVal result As Long)
    Dim x As Long
    Dim y As Long
   
    ' Debug.Print "result = " & result
    For x = 1 To 255
        For y = 1 To 255
            If (x * y = result) Then
                'Debug.Print x & " * " & y & " = " & result
            End If
        Next y
    Next x
End Sub
0
 
o0JoeCool0oAuthor Commented:
wow I didnt even have to try them all! thanks Idle! Awarding points!
0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
Those results were with the app being run in the IDE.  I also changed the loops so they went all the way to 65025 and ran the compiled version:

    Idle_Mind: 0.7402344
    shijusn: 1.162109
    pegasys: 7.439453
0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
This version is slightly faster than my previous:

Private Sub ListFactors(ByVal result As Long)
    Dim x As Long
    Dim y As Long
    Dim f(255) As Boolean
   
    Debug.Print "result = " & result
    For x = 1 To 255
        If Not f(x) Then
            If (result Mod x) = 0 Then
                y = result / x
                If y <= 255 Then
                    Debug.Print x & " * " & y & " = " & result
                    f(x) = True
                    f(y) = True
                End If
            End If
        Else
            Exit Sub
        End If
    Next x
End Sub

Good luck...
0
 
S-TwilleyCommented:
I go to sleep for a few hours and it all closes up...

Idle... did you not think about the fact that an odd target can only have odd factors... so your loop need only be:

For x = 1 To 255 Step 2

when   result Mod 2 = 1.

---------------

I know points have been awarded and all... but I was working on alternative approach which broke down a number into it's prime products... then to work out all the pairs of numbers that when multiplied make that target, you take any number of the prime products, multiply them together, and the product of the remainder is the other factor...

since it only takes a shortish time to work out all the prime-numbers between 1 and 10,000,000 (on my PC it took just over a second)... which need only be done once at the beginning of the program... you can then go through the prime numbers, continually dividing your target by that prime if its a factor, till you have all factors of the target:

e.g:

156165 = 1 * (3 * 5 * 29 * 359)

then just take any number of values within the brackets, multiply... that's your first factor... then the product of the remaining numbers if your other operand.

Just an alternative approach... although more complicated. :P ... anyway, good luck with what you're using
0
 
S-TwilleyCommented:
maybe i should open up this in a seperate thread... I was curious about those performance times you gave... were they for just finding one number's products... or all number's products within a range?

Think my competitive streak is coming thru :P... but im also interested in the logic of things like this.

sorry if this is starting to annoy people since the problem is "solved"... just unsubscribe or if that's a prob, i'll put up a seperate Q
0
 
Mike TomlinsonMiddle School Assistant TeacherCommented:
They were finding all the products of the numbers 1 thu 65025.

The test loop was originally this:

    startTime = Timer
    For r = 1 To 10000
        Call Idle_Mind(r)
    Next r
    endTime = Timer
    Label1.Caption = "Idle_Mind(): " & endTime - startTime
    Label1.Refresh

I changed the 10000 to 65025 after I submitted though.

Feel free to code away...   =)

I'm no genius and these kind of things interest me as well.
0
 
S-TwilleyCommented:
ok... i can see that you're marking off the other product using the f() array.. so not to get duplicates... but why not just go up to the sqr root of the target?

when you're just working out product factor pairs:

X * Y = Z

it's the fact that (ignoring duplicates)

X <= sqrt(Z)  and Y >= sqrt(Z)   and since the Y values are found from dividing Z by X... you can just calculate values up to and including the sqrt (rounded down).

Also... if Z is odd... the only way that   X * Y   can create an odd number is if X and Y are odd... so we don't need to test for even factors
The same doesn't apply for even Z's ... you could test for just even factors because at least one of the factors (X or Y), has to be even, but you'd have to go from 1 up to Z to test for factors (rather than up to the sqrt).

This is the simplest way of doing it (im not sure if the more complicated way using primes is more effective or not)

Here's my method (im using Idle's declarations so I don't use VB.NET stuff)
Im writing this out of the IDE... so sorry if there are a few slipups... It's a shame that the even values or result can't be made more efficient

Private Sub ListFactors(ByVal result As Long)
    Dim x As Long
    Dim y As Long
    Dim sqr_res As Long

    ' OK... the value below should be the square root of result rounded down... i forget some VB stuff
    sqr_res = Sqr(result)
    sqr_res = Trunc(result)

    Debug.Print "result = " & result
    Debug.Print "1 * " & result & " = " & result

    If result Mod 2 = 1 Then
        'if result is odd

        For x = 3 To sqr_res Step 2
            If (result Mod x) = 0 Then
                y = result / x
                Debug.Print x & " * " & y & " = " & result
            End If
        Next x
    Else
        'if result is even

        For x = 2 To sqr_res
            If (result Mod x) = 0 Then
                y = result / x
                Debug.Print x & " * " & y & " = " & result
            End If
        Next x
    End If
End Sub
0
 
o0JoeCool0oAuthor Commented:
I certainly dont mind the posts here the faster I can get this to execute the better.  essenitally I am opening a file reading the data for every byte in the file I have a number in the range of (256 * 256) and I need 2 numbers between 1-255 that multiply together to equal said number in(256*256) range.

So far all of the answers work, Id like to see a new Time test with S-Twilleys idea if u have time to add it to your test app Idle :D

u ppl are mathmatical geniuses

that or im just really stupid :D
0
 
S-TwilleyCommented:
sqr_res = Trunc(result)

should probably be

sqr_res = Fix(sqr_res)
0
 
S-TwilleyCommented:
Well I tested mine and it was a little faster than Idle's... I did write mine using VB.NET so the above code needs  de-dot-netting  (yes! it's a word!) ...  been trying to think of alternative approaches or improvements but none so far, other than working with the prime factors of a number... must be an improvement using those somehow.... as I've mentioned above, I can calculate all prime numbers up to 10 million pretty quickly (do this once when program is loaded)... and since all non-primes are made up of prime numbers multiplied together... you should be able to calculate all the factor pairs using those primes...   but it may not be more efficient in the long run!
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 11
  • 7
  • 6
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now