lil Math Help Modulus Maybe?

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

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

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

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

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

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

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

JigglyD

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 ! ! !

Adrian Sluijters

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

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

SOLUTION

Adrian Sluijters

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

oops , ignore my last post thats not correct

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)...

'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

please change this
>>Private Sub Command6_Click()
by

Private Sub Command1_Click()

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

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

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

o0JoeCool0o

ASKER

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!

ASKER CERTIFIED SOLUTION

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

o0JoeCool0o

ASKER

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

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

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

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

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

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.

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

o0JoeCool0o

ASKER

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

sqr_res = Trunc(result)

should probably be

sqr_res = Fix(sqr_res)