resending mini long-division (in case the first one got lost)

[fuzzy wozzy]

\* mini long-division *\
\* (long [2 3 5][3]) = [[7 8] [1]] *\

(define long
    N D -> (long0 (remz (rL (take (length D) N) D))
          (drop (length D) N)
           D (qL (take (length D) N) D))
        where (bigger? (take (length D) N) D)

    N D -> (long0 (remz (rL (take (+ 1 (length D)) N) D))
          (drop (+ 1 (length D)) N)
          D (qL (take (+ 1 (length D)) N) D))
        where (not (bigger? (take (length D) N) D)))

(define long0
    H N D Ans -> [(reverse Ans) [0]] where (and (= N []) (= H []))
    H N D Ans -> [(reverse Ans) H] where (= N []) 

    H N D Ans -> (long0 (remz (rL (append H [(hd N)]) D)) (tl N)
            D (append (qL (append H [(hd N)]) D) Ans))
             where (bigger? (append H [(hd N)]) D)

    H N D Ans -> (long0 (remz (append H [(hd N)])) (tl N) D (cons 0 Ans))
            where (not (bigger? (append H [(hd N)]) D)))       

       



           

[fuzzy wozzy]

each digit in the numerator can be divided by a denominator,
giving a quotient and a remainder, if dividing 16 by 3,

     0 2 <- quotients from dividing 1 by 3, and 6 by 3
3 | 1 6
     1 0 <- remainders from dividing 1 by 3, and 6 by 3

the remainder 1 is multiplied by 10 and divided by 3,
(1 x 10) / 3 = 3 with remainder of 1,
the quotient 3 is added to the quotient 2,
remainder of 1 is added to 0, remainder in the next column,
and the above becomes,

     0 5
3 | 1 6
       1

dividing 28 by 3 leaves a remainder that's bigger than the
denominator, which is adjusted by adding 1 to the quotient
and subtracting from the denominator accordingly,

     0 2
3 | 2 8
     2 2

becomes,

     0 8
3 | 2 8
       4 <- bigger than the denominator, so the answer becomes,

     0 9
3 | 2 8
       1

for multi-digits, it can work in the following ways,
first, same as above,

       0 0 0 0 <- quotients from dividing 5 by 25, 1 by 25, ... for any denominator >= 10, quotient for each digit = 0
2 5 | 5 1 7 3
       5 1 7 3 <- remainders from dividing 5 by 25, 1 by 25, ...


       0 2  0 0 <- 2 is from (5 x 10) / 25 = 2 with remainder of 0, 0 above 7 is from (1 x 10) / 25 = 0, remainder of 10
2 5 | 5 1  7 3
            17 3 <- 17 is from (10 + 7)


       0 2 0  6 <- 6 is from (17 x 10) / 25 = 6, remainder of 20
2 5 | 5 1 7  3
               23 <- 23 is from (20 + 3)


with precalculated quotients and remainders, it works out the same,
if precalculated in groups of two (could be in groups of three, four,
or any combination)

          2    2 <- quotients from dividing 51 by 25, 73 by 25
2 5 | 5 1  7 3
          1  2 3 <- remainders from dividing 51 by 25, 73 by 25


          2  0 2 <- 0 from (1 x 10) / 25 = 0, remainder 10
2 5 | 5 1  7 3
            12 3 <- 12 from (10 + 2)


          2  0  6 <- 6 is from (12 x 10) / 25 = 4 with remainder 20, 4 + 2 = 6
2 5 | 5 1  7  3
                23 <- 23 is from (20 + 3)

[fuzzy wozzy]

if a remainder is less than a denominator, the remainder is multiplied by 10 and
the resulting quotient is added to the one in the next column, likewise for the remainder,

if a remainder is greater than or equal to a denominator, then it is divided without being
multiplied by 10 first, and the resulting quotient stays within the same column, and the
remainder gets added to the one in the next column, for example, 220 / 22 = 10,

       0 0 0
2 2 | 2 2 0
        2 2 0

        0   0 0 <- the second quotient, 0, is from (2 x 10) / 22 = 0 with remainder of 20
2 2 | 2   2 0
           22 0 <- 22 is from (20 + 2), but since 22 / 22 = 1 with remainder of 0, the quotient 1 stays in the same column,

        0 1 0
2 2 | 2 2 0
              0

[fuzzy wozzy]

\* using the above method of dividing each digit by a denominator,
   (div [2 9] 3) = [[9] 2]

    timewise, dividing a 7 million-digit number by 3 using (div) takes 19.7 secs, whereas using (re) takes 7.8 secs,
    so it takes a little over twice as long, but (div) function can be extended to accommodate multi-digit divisors as well,
    but the time factor for such divisions is not yet known, this is just a proof of concept that it works as expected...
*\

(define div
    N D -> (div0 (tl N) D (quot (hd N) D) (rem (hd N) D) [(quot (hd N) D)]))

(define div0
    [] D Q R Ans -> [(remz (reverse Ans)) R]
    [X|Y] D Q R Ans -> (div0 Y D (quot X D) (+ R (rem X D))
                                          (cons (+ (quot (* R 10) D) (quot X D)) Ans))
                                                  where (< (+ R (rem X D)) D)

    [X|Y] D Q R Ans -> (div0 Y D (quot X D) (- (+ R (rem X D)) D)
                                            (cons (+ 1 (+ (quot (* R 10) D) (quot X D))) Ans))
                                                   where (>= (+ R (rem X D)) D))

[fuzzy wozzy]

please disregard the previous (div) function,
while it works correctly for a 7 million digit number as posted, such as
(re (itt0 7000000) 3) = (div (itt0 7000000) 3),

but when the number starts with something other than 0, for example (div (itt0 7000005) 3),
then an incorrect answer is given, a glitch somewhere, so I'll have to figure out where first.

[fuzzy wozzy]

\* here's a fixed version, dividing a 15 million digit-number by 7 takes 70.2 secs, compared to 33.8 secs with (re) function.
   (div [2 9] 3) = [[9] 2] *\

(define div
    N D -> (div0 (tl N) D (quot (hd N) D) (rem (hd N) D)
                            [(quot (hd N) D)]))

(define div0
    [] D Q R Ans -> [(remz (reverse Ans)) R]
    [X|Y] D Q R Ans -> (div0 Y D (quot X D)

                                           (+ (rem (* R 10) D) (rem X D))

                                           (cons (+ (quot (* R 10) D) (quot X D)) Ans))

                                                   where (< (+ (rem (* R 10) D) (rem X D)) D)

    [X|Y] D Q R Ans -> (div0 Y D (quot X D)

                                           (- (+ (rem (* R 10) D) (rem X D)) D)

                                           (cons (+ 1 (+ (quot (* R 10) D)
                                           (quot X D))) Ans))

                                                    where (>= (+ (rem (* R 10) D) (rem X D)) D))

[fuzzy wozzy]

the Q variable in div0 serves no purpose other than to demonstrate that, when removed,
the calculation time is reduced by 19 seconds, from 70 secs to 51 secs for dividing a 15 million-digit by a single digit,
but while (long) function calculates 50000-digit number divided by 4000-digit number in little over 15 minutes,
for 100000 digits it seems to go into a loop, which is why lists are considered, it isn't to handle millions of digits in
seconds, for that something like (ldx) function might be better suited, though probably not in seconds but more within
a reasonable time frame, let's say... and all this might serve as a rough conceptualization for when vectors are used,
then more production-ready functions may be found.

[fuzzy wozzy]

\* time-wise, (div1) and (long) are about the same
   (div1 [2 9][3]) = [[9][2]] *\

(define div1
    N D -> [divide by zero error] where (= [] (remz D))
    N D -> (div10 (drop (length D) N) D (rL (take (length D) N) D)
                            (qL (take (length D) N) D)))

(define div10
    [] D R Ans -> [[0] [0]] where (and (= (remz R) []) (= (remz Ans) []))
    [] D R Ans -> [(remz (reverse Ans)) [0]] where (= (remz R) [])
    [] D R Ans -> [[0] (remz R)] where (= Ans [0])
    [] D R Ans -> [(remz (reverse Ans)) (remz R)]

    [X|Y] D R Ans -> (div10 Y D
                                      (remz (append R (rL [X] D))) (cons 0 Ans))
                                                   where (not (bigger? (append R (rL [X] D)) D))

    [X|Y] D R Ans -> (div10 Y D (rL (remz (append R (rL [X] D))) D)
                                             (append (qL (append R [X]) D) Ans))
                                                     where (bigger? (append R (rL [X] D))  D))

[fuzzy wozzy]

(div1 [3 6 2] [3]) gives a wrong answer, the following gives a correct answer.

[X|Y] D R Ans -> (div10 Y D
                                   (remz (append R (rL [X] D)))

                                   (append (qL [X] D) Ans)) \* this line changed *\
                                            where (not (bigger? (remz (append R (rL [X] D))) D))

[fuzzy wozzy]

here's another easy way to do long division,

9 / 3 = 1 / (3 / 9) = 3,

7 / 3 = 2 with a remainder of 1, which is equal to saying,
7 / 3 = (6 / 3) + (1 / 3) = 2 + (1 / 3).

to calculate 7 / 3,

7 / 3 = 1 / (3 / 7) <- multiplying numerator 1 by 10, denominator (3 / 7)
                             by 10 gives,

7 / 3 = 10 / (30 / 7) = 10 / (4 + (2 / 7)) = 10 / 4.28 = 1000 / 428
      = 2 + (144 / 428) = 2.336

once the quotient is calculated, the remainder can be found by,

7 - (* 3 2) = 1.

for another example,

53 / 2 = 26 with a remainder of 1 = 26 + (1 / 2)

53 / 2 = 1 / (2 / 53) = 10 / (20 / 53) = 10 / 0.377 = 10000 / 377
       = 26 + (198 / 377) = 26.525

remainder = 53 - (* 2 26) = 1.

if instead of (10000 / 377), (1000 / 37) is used then the quotient comes
out to be 27, which is not correct since, 27 x 2 = 54 > 53.

[fuzzy wozzy]

(define re
    L N -> [denominator >= [1]] where (not (bigger? N [1]))
    L N -> [numerator >= [0]] where (not (bigger? L [0]))
    L N -> (re0 L N [] []))

(define re0
    [] _ Q R -> [[0] R] where (= [] (remz Q))
    [] _ Q R -> [(remz (reverse Q))  R]
    L N Q R -> (re0 (tl L) N
                           (append (qL (addx (remz (append R [0]))
                                                                     [(hd L)]) N) Q)
                           (rL (addx (remz (append R [0]))
                                                               [(hd L)]) N)))

(define addx
    L M -> (splita (reverse (addL L (append
                                         (make-z (- (length L) (length M))) M))))
                                                       where (>= (length L) (length M))

    L M -> (splita (reverse (addL
                                       (append (make-z (- (length M) (length L))) L) M)))
                                                       where (< (length L) (length M)))

[fuzzy wozzy]

this might work ok for divisions of large numbers because (qL) works ok for
numerators and denominators of equal length, at least up to 5 million digits.

(re [5 1 3 7 2 7] [2 2 3]) = [[2 3 0 3] [1 5 8]]

each digit in the denominator is assigned either a quotient or a zero,
except any zeroes in front of the first non-zero quotient (any zeros
in front of 2 are ignored, in this case), because a zero after the
first non-zero quotient either becomes a quotient or acts as a placeholder
for a quotient that may be found later.

                2  0 0 3 <- (qL [5 1 3] [2 2 3]) (qL [7 2 7] [2 2 3])
2 2 3 | 5 1 3  7 2 7
             6 7  0 5 8 <- (rL [5 1 3] [2 2 3]) (rL [7 2 7] [2 2 3])

repeating with the temporary remainder gives,

                3  0 0
2 2 3 | 6 7 0  5 8
                1  5 8

for the quotient, [2 0 0 3] + [3 0 0] = [2 3 0 3],
remainder is [1 5 8].

[fuzzy wozzy]

if the first quotient comes up as 0, then the subsequent digits get
either 0 or a quotient, and if each set of numbers equal to the length
of numerator gives a quotient of 0, then some other method is needed
since the temporary remainder will be the same as the original denominator.

(re [2 3 5 7 9 3] [3 1 0]) = [[7 6 0] [1 9 3]])

                0  0 0 2 
3 1 0 | 2 3 5  7 9 3
                0  6 2 0
           2 3 5  1 7 3

                0  7 5 8
3 1 0 | 2 3 5  1 7 3
                   1 9 3

quotient: [7 5 8] + [0 0 2] = [7 6 0]
remainder: [1 9 3].

[Willi Riha]

Fuzzy-Wozzy’s multiple precision division attempts have been going on now for quite a while!

I do commend his enthusiasm and perseverance, and I also acknowledge that he is writing Shen code,

albeit at a very naive level. The code is untyped, unnecessarily repetitive, and also inefficient.

Some of the functions he uses, e.g. mod, are readily available in the maths lib.

Representing multiple precision integers as lists of single digits for the purpose of manipulating them,

especially, in the context of division, is like attempting to drill a tunnel with a pen knife!

What I have seen so far, are examples of division by 3, 7 and some 3-digit ints, such as 223 and 158. What about

dividing a 100000-digit int by a 538-digit int? This is hard, and IMHO requires extensive study of

Knuth’s Algorithm D (Knuth, Seminumerical Algorithms, 2^nd ed., p 257).

Multiple-precision ints are usually represented in suitably chosen groups of 5 or 6-digits integers, depending on platform, both for efficiency and convenience. Whether a list, or a vector representation in Shen is preferred, I cannot say, without trying it. And I don’t think I will have a go, certainly not at the moment.

Willi

 

 

--
You received this message because you are subscribed to the Google Groups "Shen" group.
To unsubscribe from this group and stop receiving emails from it, send an email to qilang+un...@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at http://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

[fuzzy wozzy]

thank you for your comment,
choosing a group of 5~6 integers sounds interesting, would be nice to hear more about it,
dividing a 100000-digit number by 4000-digit number took a little over 30 minutes, maybe 33~35 minutes,
probably dividing a million-digit number is possible, providing no stack overflow and a great patience on
the part of the user.

division by length-matching, such as the example with 223 and 158, appears like it might work ok too,
even when the quotient is 0 for a unit of calculation, simply by using the method shown in (div) function,
but the remainder would need to be calculated as well, so there might be a bit of recursion involved there.

the inverse division method, where 7 /3  = 1 / (3 /7), seems like (ok, just got the result back for
dividing 100004-digit number by 538-digit number and the time was 293 secs, almost 5 minutes),
the inverse division method seems like it could work even better, esp. by minimizing the usage of unnecessary
list space with repeating numbers, i.e. instead of expressly writing out the numbers in a list format, etc, one could
find another way of doing it, but finding the remainder might not be so easy when the remainder is millions of digits long,
for example.

it's true that the functions so far have been naively done, repetitive and redundant not to mention verbose,
and certainly inefficient, which might hint at the possibility of efficiency and efficacy that could be enjoyed
when someone more knowledgeable tweaks it, but if any of the other methods work ok then inefficient might not be
an expression at least in comparison to the previous functions that have been tried, in reality, list division using multi-digit
divisor was just a fantasy even a month ago, so...

on a side note, j language from jsoftware.com, array language, is said to have stopped giving support for jdbc, j lanuguage
database, and instead the company is developing jd, a commercial j language database application, there seems to be
some kind of a perfectly harmonious symbiosis between array languages and database needs, which, by the way, shen is
naturally well suited for, among other things, array programming and database querying.

[fuzzy wozzy]

you can try it out yourself by using the (itt0) function which iterates numbers from 9 to 0 in a descending fashion,
it starts with the last digit of the value given for iteration, and gives 1 digit more than the arg calls for.

(itt0 3)
[3 2 1 0]

(itt0 25)
[5 4 3 2 1...]

(itt0 10000000) <- iteration of 10 million numbers, the value can be up to 40 million before stack overflow is reached.

(time (long (itt0 100004) (itt0 538)))

293 secs

(time (long (itt0 100007) (itt0 4035)))

(define itt0
    -1 -> [nonnegative number only]
     N -> (if (< N 0) (itt0 -1) (itt1 N -1 [])))

(define itt1
    -1 _ L -> L
    N 9 L -> (itt1 N -1 L)
    N Acc L -> (itt1 (- N 1) (+ Acc 1) (cons (+ Acc 1) L)))

[fuzzy wozzy]

the inverse or flip method feels counter-intuitive, involving way more calculations than just a straight-out division,
instead of one division calculation it requires three or more, even making smaller numbers bigger on purpose,
the conventional method stalls after a certain point and this method is considered for a possible speed gain for
larger number division, it may or may not work, but I think the conventional method reached its limit too,
all three methods, (long)/(div1)/(re), give about the same calculation time, not much difference between them,
not just timewise, but the number of digits they can handle while giving a reasonable time of calculation seems limited too,
I don't think even in the hands of someone experienced, that it's gonna make much difference, my naivete tells me,

mathematically, it seems like it would work, finding remainders may be easier than first thought, there are some minor
details that need to be ironed out, however, because even one digit off and the answer is not just wrong but it couldn't
be more wrong, I like the tunnel analogy, maybe it applies to life in general too, in some sense.

[Mark Tarver]

Try using local assignments to shorten your code

NOT

(define addx 
    L M -> (splita (reverse (addL L (append 
                                         (make-z (- (length L) (length M))) M))))
                                                       where (>= (length L) (length M))

    L M -> (splita (reverse (addL 
                                       (append (make-z (- (length M) (length L))) L) M)))

                                                       where (< (length L) (length M)))

but

(define addx 

    L M -> (let LL (length L)

                    LM (length M)

                    (if  (>= LL LM) 

                         (splita (reverse (addL L (append (make-z (- LL LM)) M)))) 

                         (splita (reverse (addL (append (make-z (- LM LL)) L) M))))

Also some types!   We 've done long division pretty thoroughly here and since Willi is the only respondent, you could probably move on.                                                     

Mark

[fuzzy wozzy]

I guess I'll have to agree,
although some of the 157 people who checked out the thread may be
too shy to make a comment or a question, overall the lack of interest
is obvious and probably most checked it out of boredom for something
more interesting or the lack thereof,
and the thoroughness of the thread seems to be more than what willi
was anticipating or expecting, that's good enough for me I guess,
and the long division method is one also used by mathetmatica from what
I remember, and if it's good enough for them, it's good enough for me.

one thing to note about continuation method, is one has to take extra care
when the remainder is [0], there may be several zeros in the quotient and
one way to be sure is to redo the calculation using several more digits to be sure,
but the inverse/flip method doesn't give away the remainder too easily and
I wasn't too keen on thinking about it too much at the moment, willi is smart
not to have tried precision integer division in shen, it's more like drilling a tunnel
through himalayas with a number 2 pencil, but I'm glad that what was presented
exceeded his expectation, which is directly attributable to shen's list/recursion,
which of course other lisp languages have, but we're talking shen here, so...

if anyone needs more arithmetic capability, which I doubt anyone would other than
university researchers and they already have maple and mathematica and what have you,
ruby can do high number calculation in seconds, maybe not hundreds of millions, but
breezy easy for tens of, to me all shen ports are an achievement of herculean efforts,
boggles the mind, shen-ruby was the only one I could get up and running just to test out
the shen in ruby, which worked as explained on the download page's short intro.
ruby rail is known to be good website builder, so maybe both javascript and ruby rail can be
featured on the website's welcome page, just my two cents.

I'll say it again, shen-elixir port might be another good one if possible, esp. for anyone interested
in distributed computing, really, dataflow/parallel computing is all fine and dandy, and they're still
the buzzword of the decade or whatever, elixir is a relatively newcomer and the impact it's making
on the programming community may be nothing short of astonishing, with a capital A.
and those with the know-how can probably do it in days not weeks, but thank you for the kind
suggestion about the code segment, it was actually a prime example of redundant and unnecessary line,
added in in panicky frenzy that the code might not work or work with a glitch, totally untrue, and the
following original function not only works just as well but looks better to me too, and it goes a few
micro seconds faster than the other two, but we may be splitting hair here,

as far as types go, if I need to I would try haskell or ml, I realized how hard and almost impossible to decipher
the inner workings of shen type systsem from the last time artella coding was asking about a very decpetively simple-looking type code
that nearly made things go haywire until someone kindly suggested a seemingly ad-hoc yet simple modification, which worked,
which made me realize that if tail-recursion seemed insurmountable until, by pure chance, I made it work for the
iteration function (it0), and never wanted to touch it again, not even if the function name looked funny to some,
I knew I needed more hand-holding learning types that might be afforded via haskell or ocaml or any other dozen popular
languages, but that's just me, I guess...

(define re
    L N -> [denominator >= [1]] where (not (bigger? N [1]))
    L N -> [numerator >= [0]] where (not (bigger? L [0]))
    L N -> (re0 L N [] []))

(define re0
    [] _ Q R -> [[0] R] where (= [] (remz Q))
    [] _ Q R -> [(remz (reverse Q))  R]
    L N Q R -> (re0 (tl L) N

                             (append (qL (remz (append R [(hd L)])) N) Q)
                             (rL (remz (append R [(hd L)])) N)))