= Karatsuba operand splitting
{c}
{title2=$x=aB^m+b,\quad y=cB^m+d$}
Fix an <integer> base $B\geq2$. Let $x,y\geq0$ have at most $n$ digits in <positional notation>, treating zero as one digit. For $n>1$, set $m=\lceil n/2\rceil$ using the <ceiling function>, and $q=B^m$. <Euclidean division> gives
$$
a=\lfloor x/q\rfloor,\quad b=x-aq,\qquad c=\lfloor y/q\rfloor,\quad d=y-cq,
$$
where $0\leq b,d<q$ and $0\leq a,c<B^{n-m}$. The <floor function> selects the high block; the remainder selects the low block. Both operands must use the same $q$, including when their actual digit lengths differ.
For odd $n$, the low block has $m$ digit positions and the high block has $n-m=m-1$. Leading zero padding aligns a shorter operand without changing its <integer> value. Padding to a power-of-two length is optional: the split itself works for every $n$. If power-of-two padding is used, the padded length is less than twice the original length, so it changes only a constant factor in the <asymptotic analysis>.
Back to article page
