real-world division
86 views
Skip to first unread message
fuzzy wozzy
May 4, 2015, 1:03:58 PM5/4/15
to qil...@googlegroups.com
a slight modification to (div) method for multi-digit divisors may speed up the calculation time,
for a division of 100000 digit by 583 the time may be reduced by half or more,
if I wasn't feeling so lazy I would be able to show it to be so, even.
the modification was explained in the last post sent that somehow never got posted, but
whereas with conventional methods such as (long)/(div1)/(re) the time increases exponentially
as the numbers get larger, both numerators and denominators, the modified version of (div)
would show a linear timeline increase.
of course this is nothing compared to computers that can do 27500 trillion calculations per second,
but it would be a lot more than what there was a month ago in terms of list divisions at least...
for a division of 100000 digit by 583 the time may be reduced by half or more,
if I wasn't feeling so lazy I would be able to show it to be so, even.
the modification was explained in the last post sent that somehow never got posted, but
whereas with conventional methods such as (long)/(div1)/(re) the time increases exponentially
as the numbers get larger, both numerators and denominators, the modified version of (div)
would show a linear timeline increase.
of course this is nothing compared to computers that can do 27500 trillion calculations per second,
but it would be a lot more than what there was a month ago in terms of list divisions at least...
fuzzy wozzy
May 4, 2015, 10:20:55 PM5/4/15
to qil...@googlegroups.com
to apply (div) method to multi-digit divisor using a simple example,
(long [6 7 3 4] [2 2]) = [[3 0 6] [2]]
find intermediate quotients and remainders for each set of numerators
whose length is equal to the length of the denominator, unequal lengths
are ok too, but finding quotients and remainders are faster with equal
lengths.
[3 0 1] is a list of intermediate quotient, next multiply the remainder from
the first set by 10 and divide the result by the divisor, collect the
quotient in a separate list and repeat the process by using the new
remainder, as many times as the number of digits in the second set, which,
in this case, is 2.
the last remainder from this calculation is added to the remainder in the
second set, and if the result is bigger than the divisor, then the divisor
is subtracted from it and the last quotient is incremented by one.
to find the quotient, add the two quotient lists found above and normalize
the combined list so that no digit in the list is greater than 9.
3 0 1 <- intermediate quotient of dividing 67 by 22, and 34 by 22
2 2 | 6 7 3 4
1 1 2 <- intermediate remainder of dividing 67 by 22, and 34 by 22
(1 x 10) / 22 = 0 with a remainder of 10,
(10 x 10) / 22 = 4 with a remainder of 12.
the second list of quotient, [0 4], is added to the first list, [3 0 1].
[3 0 1] + [0 4] = [3 0 5].
the last remainder, 12, is added to the remainder in the second set,
12 + 12 = 24, and 24 is bigger than the divisor, so remainder is
24 - 22 = 2, and the quotient list is incremented by one,
[3 0 5] + [1] = [3 0 6].
quotient = [3 0 6], remainder = [2].
different ways of grouping may be used for more efficient calculation,
but this is the basic method.
(long [6 7 3 4] [2 2]) = [[3 0 6] [2]]
find intermediate quotients and remainders for each set of numerators
whose length is equal to the length of the denominator, unequal lengths
are ok too, but finding quotients and remainders are faster with equal
lengths.
[3 0 1] is a list of intermediate quotient, next multiply the remainder from
the first set by 10 and divide the result by the divisor, collect the
quotient in a separate list and repeat the process by using the new
remainder, as many times as the number of digits in the second set, which,
in this case, is 2.
the last remainder from this calculation is added to the remainder in the
second set, and if the result is bigger than the divisor, then the divisor
is subtracted from it and the last quotient is incremented by one.
to find the quotient, add the two quotient lists found above and normalize
the combined list so that no digit in the list is greater than 9.
3 0 1 <- intermediate quotient of dividing 67 by 22, and 34 by 22
2 2 | 6 7 3 4
1 1 2 <- intermediate remainder of dividing 67 by 22, and 34 by 22
(1 x 10) / 22 = 0 with a remainder of 10,
(10 x 10) / 22 = 4 with a remainder of 12.
the second list of quotient, [0 4], is added to the first list, [3 0 1].
[3 0 1] + [0 4] = [3 0 5].
the last remainder, 12, is added to the remainder in the second set,
12 + 12 = 24, and 24 is bigger than the divisor, so remainder is
24 - 22 = 2, and the quotient list is incremented by one,
[3 0 5] + [1] = [3 0 6].
quotient = [3 0 6], remainder = [2].
different ways of grouping may be used for more efficient calculation,
but this is the basic method.
fuzzy wozzy
May 12, 2015, 9:17:03 PM5/12/15
to qil...@googlegroups.com
currently this method is twice slower than the regular ones, with potential of being faster by a factor of 10000 or more.
Mark Tarver
May 13, 2015, 10:26:03 AM5/13/15
to qil...@googlegroups.com, swtch...@gmail.com
I'm happy to accept posts, but I feel that you have posted so many posts on this subject w.o. reply, and it is time to draw a line. I think if you have posted 3 posts in a thread with no response, the proper thing is to start something else.
Mark
Reply all
Reply to author
Forward
0 new messages