How many digit products

divide and conquer recursion memoization counting

CPython stores a long integer in 30-bit “digits” and multiplies two numbers the school way if the smaller has at most 70 such digits, and otherwise by Karatsuba: it cuts the numbers in half and makes three multiplications of halves. How many multiplications of individual digits will multiplying two numbers of a million decimal digits each take? Let us count by a simplified model.

Let both numbers be n digits long, and the cutoff t. If n ≤ t, the numbers are multiplied the school way: n² digit multiplications. Otherwise the low half of each number is ⌊n/2⌋ digits, the high half ⌈n/2⌉, and three multiplications are made: low by low, high by high, and the sum of the halves by the sum of the halves. The sum of the halves may come out one digit longer than the high half; we assume it always does, that is, its length is ⌈n/2⌉ + 1. Each of the three multiplications is made in the same way. How many digit multiplications will there be in all?

Input

The first line holds the number of questions q (1 ≤ q ≤ 10,000). Then come q lines of two numbers: the length n and the cutoff t (1 ≤ n ≤ 10⁹, 3 ≤ t ≤ 10⁹).

Output

For each question, the number of digit multiplications, on a separate line. The answer fits in a 64-bit integer.

Examples

Example 1

Input

5
1 3
4 3
100 70
140 70
1000 1000000000

Output

Limits

Time · Python: 5000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Write the number of multiplications as a function: M(n) = n² for n ≤ t, otherwise M(⌊n/2⌋) + M(⌈n/2⌉) + M(⌈n/2⌉ + 1). Straight recursion is correct. How many calls will it make with n = 10⁹ and t = 3?

2Hint 2

On the order of 3^{log₂ n} ≈ n^1.585 calls, tens of trillions for a billion. But look at which arguments occur on one level of the tree: they are all close to n/2^k. How many distinct ones are there among them?

3The idea

On level k the arguments lie in a narrow range from ⌊n/2^k⌋ to ⌈n/2^k⌉ plus a small addition from the “+1”, and there are only a few distinct values there. So the whole tree has a few dozen distinct subproblems per level, a few hundred in all, although there are trillions of calls. Remember the answer for each n (memoisation), and each subproblem is computed once.

4Walkthrough

A recursive function with a dictionary: if n ≤ t, return n²; if the answer for n is already there, return it; otherwise compute the sum of the three and remember it. The dictionary is separate for each question, because the answer depends on the cutoff.

Why there are few arguments per level. Let all the arguments of a level lie in the range [a, a + d]. Their children, ⌊x/2⌋, ⌈x/2⌉ and ⌈x/2⌉ + 1, lie in [⌊a/2⌋, ⌈(a + d)/2⌉ + 1], a range of length at most d/2 + 2. Starting with d = 0, the width never exceeds four, and each level has at most five distinct arguments.

The problem also shows what the model “the sum is always one digit longer” costs. For two numbers of a million decimal digits each, 110,731 thirty-bit digits, with cutoff 70 it comes to 533,872,809 digit multiplications, while long multiplication would take 110,731² ≈ 1.23·10¹⁰: 23 times more.

4+Solution

5Complexity

There are log₂(n/t) ≤ 30 levels with at most five distinct arguments each, so at most about a hundred and fifty computations per question, about one and a half million for all questions. Without memoisation, Θ((n/t)^{log₂ 3}) calls.

6Common mistakes

Recursion without memory. Correct, but it goes through the whole tree: on the fifth test with t = 3 and n around a billion, trillions of calls.
A formula instead of counting. 3^log₂(n/t)·t² is right only for powers of two and without the “+1”; the rounding of halves and the extra digit of the sum change the answer.
Shared memory for different cutoffs. M(n) with cutoff 70 and with cutoff 16 are different numbers; the dictionary cannot be carried between questions with different t.
Overflow. Answers go up to 5·10¹⁶: they do not fit in 32 bits, but fit in 64.

Algorithms behind it

NUM Algorithm Karatsuba multiplication Three multiplications of halves instead of four: n^1.585 instead of n², in CPython, Go and GMP. O(n^1.585) 2 problems TEC Technique Memoization Remember a function’s answer for each set of arguments so as not to compute it again: an exponential turns into a polynomial. O(the number of distinct arguments × the work per call) 2 problems