Eu sei que foi comprovado NP-completo, e tudo bem. Atualmente, estou resolvendo isso com branch e bound, onde defino o limite superior inicial para o número de multiplicações que levaria o algoritmo binário / quadrado binário normal e ele fornece as respostas corretas, mas não estou satisfeito com a execução tempo (pode demorar alguns segundos para números em torno de 200). Sendo este um problema NP-completo, não estou esperando nada espetacular; mas muitas vezes existem truques para controlar um pouco o tempo real.

Existem maneiras mais rápidas de fazer isso na prática? Se sim, o que são?