Lines Matching full:beta
419 with m>=0 and n>0 (in base beta = 2^GMP_LIMB_BITS).
424 {Here (q[m-1]*beta^(m-1)+...+q[j]*beta^j) * b[0] + r*beta^j =
425 = a[m-1]*beta^(m-1)+...+a[j]*beta^j und 0<=r<b[0]<beta}
426 j:=j-1, r:=r*beta+a[j], q[j]:=floor(r/b[0]), r:=r-b[0]*q[j].
429 We have a/b < beta^(m-n+1).
432 r=[r[m],...,r[0]], b=[b[n-1],...,b[0]] with b[n-1]>=beta/2.
433 For j=m-n,...,0: {Here 0 <= r < b*beta^(j+1).}
435 q* := floor((r[j+n]*beta+r[j+n-1])/b[n-1]).
436 In case of overflow (q* >= beta) set q* := beta-1.
437 Compute c2 := ((r[j+n]*beta+r[j+n-1]) - q* * b[n-1])*beta + r[j+n-2]
439 {We have 0 <= c2 < 2*beta^2, even 0 <= c2 < beta^2 if no overflow
440 occurred. Furthermore 0 <= c3 < beta^2.
442 r[j+n]*beta+r[j+n-1] - q* * b[n-1] >= beta, i.e. c2 >= beta^2,
444 While c3 > c2, {Here 0 <= c2 < c3 < beta^2}
445 Put q* := q* - 1, c2 := c2 + b[n-1]*beta, c3 := c3 - b[n-2].
447 Put r := r - b * q* * beta^j. In detail:
451 r[j+i]:=r[j+i]-(u mod beta) (+ beta, if carry),
452 u:=u div beta (+ 1, if carry in subtraction)
454 {Since always u = (q* * [b[i-1],...,b[0]] div beta^i) + 1
455 < q* + 1 <= beta,
516 beta^(m-1) <= a < beta^m ==> beta^(m-2) <= a/b < beta^m */
549 beta^(m-1) <= a < beta^m, beta^(n-1) <= b < beta^n ==>
550 beta^(m-n-1) <= a/b < beta^(m-n+1). */
668 mp_twolimb_t b_msdd = /* b[n-1]*beta+b[n-2] */
671 j counts down, b is unchanged, beta/2 <= b[n-1] < beta. */
678 /* Divide r[j+n]*beta+r[j+n-1] by b[n-1], no overflow. */
687 /* Overflow, hence r[j+n]*beta+r[j+n-1] >= beta*b[n-1]. */
688 q_star = (mp_limb_t)~(mp_limb_t)0; /* q* = beta-1 */
689 /* Test whether r[j+n]*beta+r[j+n-1] - (beta-1)*b[n-1] >= beta
690 <==> r[j+n]*beta+r[j+n-1] + b[n-1] >= beta*b[n-1]+beta
691 <==> b[n-1] < floor((r[j+n]*beta+r[j+n-1]+b[n-1])/beta)
692 {<= beta !}.
694 (Otherwise, r[j+n]*beta+r[j+n-1] - (beta-1)*b[n-1] < beta
695 <==> floor((r[j+n]*beta+r[j+n-1]+b[n-1])/beta) = b[n-1] ) */
704 c1 = (r[j+n]*beta+r[j+n-1]) - q* * b[n-1] (>=0, <beta). */
706 mp_twolimb_t c2 = /* c1*beta+r[j+n-2] */
712 b[n-1]*beta+b[n-2]. Because of b[n-1]*beta+b[n-2] >= beta^2/2
724 /* Subtract r := r - b * q* * beta^j. */
738 /* Here 0 <= carry <= beta*q* + beta-1. */
