Solved

# lil Math Help Modulus Maybe?

Posted on 2005-04-06
434 Views
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
Question by:o0JoeCool0o

LVL 14

Assisted Solution

hi
'try this
'Place a
'           Command button
'           Text box
' and a
'           ListBox
' to ur form and use this code
'=================================

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

LVL 85

Expert Comment

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

LVL 12

Expert Comment

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

LVL 14

Expert Comment

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

LVL 12

Expert Comment

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

LVL 12

Expert Comment

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

LVL 12

Expert Comment

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

LVL 3

Expert Comment

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

LVL 7

Expert Comment

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

LVL 14

Expert Comment

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

LVL 7

Assisted Solution

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

LVL 14

Expert Comment

oops , ignore my last post thats not correct
0

LVL 12

Expert Comment

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

LVL 14

Expert Comment

' 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

LVL 14

Expert Comment

>>Private Sub Command6_Click()
by

Private Sub Command1_Click()

0

LVL 12

Expert Comment

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

LVL 85

Expert Comment

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

LVL 85

Expert Comment

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

LVL 4

Author Comment

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

LVL 85

Accepted Solution

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

LVL 4

Author Comment

wow I didnt even have to try them all! thanks Idle! Awarding points!
0

LVL 85

Expert Comment

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

LVL 85

Expert Comment

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

LVL 12

Expert Comment

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

LVL 12

Expert Comment

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

LVL 85

Expert Comment

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

LVL 12

Expert Comment

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

LVL 4

Author Comment

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

LVL 12

Expert Comment

sqr_res = Trunc(result)

should probably be

sqr_res = Fix(sqr_res)
0

LVL 12

Expert Comment

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

Iâ€™ve seen a number of people looking for examples of how to access web services from VB6.  Iâ€™ve been using a test harness I built in VB6 (using many resources I found online) that I use for small projects to work out how to communicate with web servâ€¦
Background What I'm presenting in this article is the result of 2 conditions in my work area: We have a SQL Server production environment but no development or test environment; andWe have an MS Access front end using tables in SQL Server but we aâ€¦
Get people started with the utilization of class modules. Class modules can be a powerful tool in Microsoft Access. They allow you to create self-contained objects that encapsulate functionality. They can easily hide the complexity of a process fromâ€¦
This lesson covers basic error handling code in Microsoft Excel using VBA. This is the first lesson in a 3-part series that uses code to loop through an Excel spreadsheet in VBA and then fix errors, taking advantage of error handling code. This lâ€¦