Như ta đã biết với a và b là 2 số nguyên a*b = a*(b-1)+a khi b>0 cách làm này cũng vẫn sẽ mất b bước thực hiện. Tượng tự ta có tính chất sau trong phép nhân a*b=a*(b/2)+a*(b/2) Từ đó: ta có thể phân tích a*b như sau: a*b = a*(b/2)+a*(b/2) khi b chẵn a*b= a*(b/2) + a*(b/2)+a khi b lẻ Với tính chất này tương tự như lũy thừa ta có thể tính a*b bằng cách tính a*(b/2) mà khong cần tính a*(b-1)+a... từ đó ta có tính a*b với độ phức tạp là O(log(n)) int bin_multiplication ( int a , int b ) { int res = 0 ; while ( b > 0 ) { if ( b % 2 == 1 ) res = res + a ; a = a + a ; b = b >> 1 ; // b=b/2 } return res ; } - Đối với cách làm này ta không chỉ tính toán a*b với độ phức tạp là O(log(n)) mà ta có thể thông qua cách làm này để xử lý khi lấy 2 số lớn nhân nhau và mod cho một số m -Ắt hản chúng ta đã từng gặp một số bài toán yêu cầu modulo đáp án cho một số m t