im still trying to optimise my app.(it is deeling with bignumbers) I found something that would make a big speed difference but im having trouble understanding the code enough to impliment it. It doesn't help that the person that wrote it didn't comment anything.
I want to move the first call texttobignumber out of this sub and call it only when teststring1 changes. however it seems other subs are using the same variables and arrays. I know this meens adding another array but everytime I start trying to follow this code I get lost any help would be greatly appretiated.
VB Code:
Public Sub divide_nums()
Dim a(MaxLength) As Long
Dim b(MaxLength) As Long
Dim c(MaxLength) As Long
Dim d(MaxLength) As Long
Dim LengthA As Long
Dim LengthB As Long
Dim LengthC As Long
Dim LengthD As Long
Dim dumbnum As String
Call TextToBigNumber(teststring1, a, LengthA) ' this one needs moved out of this sub
If you want to optimize all that, then you have to change the whole concept from using strings. He works with an array of long 4-digits wide, (0-9999), that's what TextToBigNumber() does, just divide the string to 4 digits each. A long can store more than that since its 32 bits wide so using just 4 digits is very very inefficient. Didn't look at all functions, but Div reverts value back to string and works with strings so makes you wonder why the trouble with assigning to a long array.
Try to come up with another scheme and work from the ground up. Such as using byte array to store the digits in reverse. sample addition would then be a loop where
intdigit = (bytA(0) + bytB(0) + intCarry) \10
intcarry = (bytA(0) + bytB(0)) mod 10
Last edited by leinad31; Jan 17th, 2007 at 02:03 AM.
leinad31- thanks for the reply. my understanding of why it is using 4 digits wide is when you muliply a 4 digit number (16 bit)by a 4 digit number (16 bit)you may get up to an 8 digit number(32bit).
it is mainly the division I need to speed up. I am doing several thousand divides on the same number before changing it so if I could stop reconvering it every divide it should speed things up( i think)
thanks
leinad31- thanks for the reply. my understanding of why it is using 4 digits wide is when you muliply a 4 digit number (16 bit)by a 4 digit number (16 bit)you may get up to an 8 digit number(32bit).
Largest 4-digit number is 9999 which multiplies to 99980001, so you're right there...however, 9999 isn't a 16-bit number *exactly*, as 65536 is 16 bit, 32768 is 15 bit, 16384 is 14 bit (which is where 9999 fits in as the next one is 8192 which is lower than the value)...if 9999 is 14 bit then 99980001 is either 27 bit or 28 bit.
Not that that is an important point to make...if you're planning to include compression of the values within the program though, this would make a lot of difference (I'd assume you're not, it's not the frontmost thought in most people's minds and unless you're working with many millions of numbers it's not worth doing)
(note, the bit levels are from memory, so I can't guarantee they're right :-))
I love helping noobs with their VB problems (probably because, as an amateur programmer, I am only slightly better at VB than them :-)) but if you SERIOUSLY want to get help for free from a community such as VBForums, you have to first have a grounding (basic knowledge) in VB6, otherwise you're way too much work to help...You've got to give a little if you want to get help from us, in other words!
And we DON'T do your homework. If your tutor doesn't teach you enough to help you make the project without his or her help, FIND A BETTER TUTOR or try reading books on programming! We are happy to help with minor things regarding the project, but you have to understand the rest of it if you want our help to be useful.
What kind of text numbers are you dealing with in the first place?
What do they look like?
they are positive whole numbers. no negatives, no decimals. I will need the remainder from the divisions.
smUX- you are right i wont be doing any compression on the numbers for storage. even though i am dealing with millions of numbers most of them wont get stored. I will only be storing a few that meet certain requirments.
i realize VB is not the best suited for this however it is what i have at the moment. unfortuanatly I cant really go into what the calculations are for right now. I have to call it a night as it is almost 1am here
Scientific calculations are not often integer... it's the number of precision places. If you need a very large number you use both the integral and precision digits to take advantage of much larger numbers than you could normally.
Scientific calculations are not often integer... it's the number of precision places. If you need a very large number you use both the integral and precision digits to take advantage of much larger numbers than you could normally.
all of my numbers are integer before the division and im after the remainder as a remainder not a decimal.
Ok assuming we'll only work with whole numbers for now. What he does is segragate the string into 4 digits. Consider 1234 5678 9012 and 9876 5432... the problem with those numbers is the alignment, 1st group of 1st number (x10^8) is aligned with first group of second number (x10^4). That is why he reverses their assignment in the array giving 9012 5678 1234 and 5432 9876. He then does computations on those arrays.
1) My first suggestion would be to use dynamic arrays instead of fixed sized array. You will end up with less iterations or you no longer have to maintain variables that track the position of ubound for each array since you can use ubound() function. After getting the arrays, you need to make them of equal size to simplify iteration (they have same ubound). You just redim preserve the smaller array to the size of the bigger array, which will produce array elements of value zero such that 5432 9876 -> 5432 9876 0 (Note: not 0000 since your transferred string to numeric (long) array).
2) Addition would then be just adding the corresponding array elements of addend arrays. You will end up with values greater than 4 digits or greater than 9999. Rather than checking the length of the number when cast to string just check if > 9999 and carry the excess digits to the next array element. If 9999 + 1111 11110 then carry 1 to next array element and update current array element to 1110. Or current is value Mod 10000, and carry is value \10000, note that we work with the numeric value rather than casting to string and checking length. So we need a procedure that iterates through the working array and does the carry operation.
Public Sub ApplyCarry(ByRef MyArr() As Long)
During carry if next array element does not exist then you need to create another array element to accept the carry. ReDim preserve the array and apply the carry.
Last edited by leinad31; Jan 17th, 2007 at 09:47 PM.
3) Note that the addition is inefficient cause long can accept up to 2^31-1 (2^32 results in negative values) which is 9 digits. This is one optimization method, we need two number "splitters"; 4 digits for multiplication and 8 digits for the rest (addition, subtraction, division). We can further optimize by using currency data type instead of just long so we can get more digits. Will check how many digits we can use with an array of currency. It should be max num digits possible less 1 digits to accomodate carry less 4 digits used as decimal places.
So we also need a procedure that splits the number in string (assumed valid input, or another procedure to clean the string called from this procedure) to an array of numerics. If we use dynamic arrays instead of fized sized arrays then:
And if we use digit_group_counter (init zero) when getting digits from left to right then we assign to array with
array(ubound(array) - digit_group_counter) 'we subtract so array is populated in reverse
By working with more digits then we reduce the number of iterations through the numeric array. As mentioned earleri, I suggest using currency, just drop the decimals when converting back to string.
Last edited by leinad31; Jan 17th, 2007 at 10:25 PM.
4) For subtraction we can again work with more than 4 digits to increase efficiency. We now need a procedure that does the borrow for us.
Public Function DoBorrow(ByRef MyArr(), ByVal GroupIndex As Long) As Boolean
You get MyArr() and make a working copy of the array in the procedure. GroupIndex tells us at which array element initiates the borrow. We then iterate (starting at GroupIndex) to ubound -1 and update the working array. We deduct 1 from next array element and update current array element (eg. If working with 8 digits then we add 100000000 to current array element). After iteration if ubound array element is less than zero (-1) then we can't borrow, function returns False, and MyArr() is untouched. If borrow was successful then MyArr is updated with values of working array.
Implementation I suggested above assumes both numbers are positive. Calling procedure should handle the signs and pass only positive numbers (no leading "-"). The same goes for addition actually, forgot to mention earlier.
The borrow is used to update the array of the minuend (subtrahend array remains the same during subtraction) if during subtraction iteration the current subtrahend group is more than then corresponding minuend group. After carry (if successful) subtraction continues.
Last edited by leinad31; Jan 17th, 2007 at 10:06 PM.
5) I suggest your addition and subtraction procedures return the numeric (long/currency) array instead of immediately converting back to string. This will facilitate successive additions/subtractions and you don't need to convert back to array the subtotal/current difference. You just pass the result array to another addition/subtraction operation.
So we now also need another procedure to convert numeric array to string. I suggest redimming a string array to same size as numeric array, then copy values formatted to appropriate number of digits (padded with leading zeroes if necessary) in reverse order.
Then do another pass on string array (from zero to ubound) to remove excess leading zeroes. Then Join(string_array, "") to concatenate the digits groups.
Last edited by leinad31; Jan 18th, 2007 at 11:52 AM.
6) Division is implemented as repeated subtractions... if you already did the optimization for subtraction mentioned earlier then division will also be faster. You just count how many subtractions you've performed (start at 1), and what's left of the dividend after subtractions is the remainder.
There are division shortcuts dividend = 0, divisor = 0, divisor = 1. Since the user could pass strings with zeroes padded, and zeroes are padded during array resize (when we made 2 working arrays, eg. addends, of same size), might as well create two more procedures IsZero(MyArr(), GroupIndex) and IsOne(MyArr()) that will check that the sum from current element to ubound (for IsZero, IsOne always starts at array index zero) is zero or one and returns apprpriate boolean value.
The division becomes complicated cause your gonna maintain the quotient in the numeric array format.
I'll continue later (division and multiplication) cause I have to go in a few minutes. Hopefully someone will post "I'll do the addition" or "I'll do currency array creation procedure" and such so you have procedures in the new scheme to work with. Ciao!
Last edited by leinad31; Jan 17th, 2007 at 10:28 PM.
I would suggest that when you break the numbers into the four characters and place into the array, why not just convert them into a two byte numeric integer. All computations after that would be much faster.
Hmmm... not totally sure which will produce better results; less iterations or using changing data type. I'm assuming the former. We can make the procedures dependent on digits_per_group so they can continue processing whatever the numeric array data type so shifting from one data type to another is facilitated if that optimizes the code better compared to increasing number of digits per group.
Regardless of data type for numeric array, assigning more than 4 digits (for long data type) for addition, subtraction and division still holds though as an optimization method. If we downgrade to integer or accomodate 4 digits in a smaller data type, the number of iterations stays the same.
Last edited by leinad31; Jan 17th, 2007 at 10:41 PM.
I am considering doing multiplication as a matrix... need to think about it some more though. Be back later (or a few days after whichever comes first). Ciao!
The easiest way to do multiplication is shifting. Meaning you wouldvget the base 10 of all the parts of the multiplier and shift the large number by that many positions then you will only have to deal with the units.
7 x 1000 - Shift 3 positions then multiply by 7
5 x 100 - Shift 2 positions then multiply by 5
5 x 10 - Shift 1 position then multiply by 5
7 x 1 - Shift 0 positions then multiply by 7
This I believe would yield the shortest iterations...
Yes something like that but will work with the 4-digit (or other digits_per_group count) groups. The shift will be in terms of array indices rather than counts of zeroes. Still working on how to collect the products and how to use/modify ApplyCarry() to get the final product. The matrix is based on (a+b+c)(d+e+f) = ad + ae + af + bd + be + bf + cd + ce + cf adjusted for zeroes (or array indices).
964652 x 7557
96 x 7557 @array indices 1,0 = 72 5472 assign to result array index 1=0
4652 x 7557 @array indices 0,0 = 3515 5164 assign to result array index 0+0
That's all theoretical for now, still have to check algorithm against other combinations, matrix dimensions (especially the determiniation of array index in result array). ApplyCarry() seems to require same digits_per_group as that used in creating multiplication numeric arrays. Result array size ought to be just minuend array size.
7) After thinking about division (related subtraction) some more it would be best to also return a flag that the difference is negative so subtraction will still return a result even if subtrahend > minuend. This can be determined by DoBorrow = False during subtraction iteration. When that happens, we swap the subtrahend and minuend, set negative number flag to True, and again perform subtraction (start again) on the swapped values.
Public Function Subtract(Minuend() As data_type, Subtrahend() as data_type, byref Remainder(), ByRef IsNegative As Boolean) As data_type()
So during division (repetitive subtraction), we can just check returned value for IsNegative to know when to stop the repetitive subtraction.
Still need to think more on how to populate the subtraction count numeric array, which will be returned by the function, in division. Remainder() will just equal the updated (values subtracted) minuend()
Last edited by leinad31; Jan 18th, 2007 at 02:03 AM.
looking at this code it I am not seeing how it is setting the data to my array. it looks like it should be putting it all in a(). can someone explain why it doesn't?
VB Code:
Public Sub TextToBigNumber(Tekst As String, a() As Long, LengthA As Long)
I explained that in post #16 first paragraph. He's doing string manipulation getting 4 digits at a time starting from the end of the string. He then transfers the digits, converts string to long, to the fixed sized array (or dynamic array presized to a determined value, have to check later which he did) starting at array index zero. The other half of the If-Else structure (part with ostatak) just handles strings with number of digits not a multiple of 4 such as 5,6, or 7 digits.
Last edited by leinad31; Jan 18th, 2007 at 01:53 AM.
If your gonna really optimize then best start from scratch to work with more digits. Design I gave you is based on his numeric array concept... we will extend it to handle more digits and convert math algorithm to actual number crunching rather than digits as string testing (which previous author did). For you immediate needs (extended Mod), we will need to develop Division(), Subtraction(), DoBorrow(), ApplyCarry(), CreateNumArray(based on digits_per_group count) in reverse order.
looking at this code it I am not seeing how it is setting the data to my array. it looks like it should be putting it all in a(). can someone explain why it doesn't?
VB Code:
Public Sub TextToBigNumber(Tekst As String, a() As Long, LengthA As Long)
Dim i As Long
Dim Prvi As String
Dim MaxLengthPrvi As Long
Dim ostatak As Long
' remove any spaces from number
Prvi = Trim$(Tekst)
a(0) = 0
MaxLengthPrvi = Len(Prvi)
If (MaxLengthPrvi \ 4) * 4 = MaxLengthPrvi Then
LengthA = MaxLengthPrvi \ 4
For i = 1 To LengthA
a(i) = Mid$(Prvi, MaxLengthPrvi - i * 4 + 1, 4)
Next i
Else
LengthA = MaxLengthPrvi \ 4 + 1
ostatak = MaxLengthPrvi Mod 4
For i = 1 To LengthA - 1
a(i) = Mid$(Prvi, MaxLengthPrvi - i * 4 + 1, 4)
Next i
a(LengthA) = Mid$(Prvi, 1, ostatak)
End If
End Sub
No error messages? You may need to convert to long
thanks for the quick reply. I am actually looking at taking out the trim$ as the strings are already numeric with no added spaces no commas or decimals ect.... and that just adds an unneeded step at this point.
Test this if it gives same result. Number of digits per group is passed as an argument.
Let's try using Long for now since its most appropriate for 32 bit PCs and I forgot that we will be using \ and Mod for ApplyCarry() so it has to be long type..
Last edited by leinad31; Jan 18th, 2007 at 04:09 AM.
more optimising
Reply With Quote
Originally Posted by n1ghtowl
Re: more optimising
