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

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

# 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
• 11
• 7
• 6
• +3
3 Solutions

Commented:
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

Middle 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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
oops , ignore my last post thats not correct
0

Commented:
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

Commented:
' 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

Commented:
>>Private Sub Command6_Click()
by

Private Sub Command1_Click()

0

Commented:
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

Middle School Assistant TeacherCommented:

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

Middle 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

Author 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

Middle 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

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

Middle 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

Middle 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

Commented:
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

Commented:
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

Middle 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

Commented:
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

Author 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

Commented:
sqr_res = Trunc(result)

should probably be

sqr_res = Fix(sqr_res)
0

Commented:
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

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