Algoritmo de Karatsuba em C

Trabalho 01 Algoritmo de Karatsuba Pedro Hokama Ana Andrade CTCO04 2025s2 Prazo de entrega 19092025 Data para entrega atrasada sem penalidade 26092025 Importante Nao olhe codigos de outros ou da internet Exceto o que e fornecido Em caso de plagio fraude ou tentativa de burlar o sistema sera aplicado nota 0 na disciplina aos envolvidos O Trabalho pode ser realizado em duplas Entretanto essas duplas serao fixas ate o final do semestre Alguns alunos podem ser solicitados para explicar com detalhes a implementacao Este trabalho devera ser implementado em linguagem C O codigo deve ser submetido APENAS pelo lider da dupla em httpsruncodeshokamacombr Seu programa deve executar no runcodes em menos de 1 segundo Passar em todos os testes do runcodes nao e garantia de tirar a nota maxima Sua nota ainda depende do cumprimento das especificacoes do trabalho qualidade do codigo clareza dos co mentarios boas praticas de programacao e entendimento da materia O problema da multiplicacao de inteiros e fundamental em diversas areas como criptografia aritmetica de precisao e algoritmos numericos O metodo tradicional de multiplicacao possui com plexidade quadratica pois cada dıgito de um operando deve ser combinado com todos os dıgitos do outro Embora essa abordagem seja simples e intuitiva ela se torna pouco eficiente quando os numeros envolvidos possuem centenas ou milhares de dıgitos O algoritmo de Karatsuba surge como uma alternativa mais sofisticada baseada na tecnica de di visao e conquista A ideia central consiste em decompor os operandos em partes menores e reorganizar os calculos de forma a reduzir o numero de multiplicacoes necessarias compensando com operacoes adicionais de soma e subtracao Essa estrategia permite diminuir a complexidade assintotica do pro cesso tornando o algoritmo consideravelmente mais eficiente do que o metodo tradicional para inteiros de grande magnitude Neste trabalho a tarefa proposta e implementar o Algoritmo de Karatsuba para multiplicacao de inteiros de modo a compreender na pratica sua logica de divisao e conquista e observar como seu desempenho se compara ao da multiplicacao tradicional Para isso sera fornecido um codigo contendo a multiplicacao tradicional Provavelmente mesmo usando a estrategia de divisao e conquista quando n se torna pequeno pode valer mais a pena usar a multiplicacao tradicional do que chamar recursivamente o algoritmo de Karatsuba 1 Seu programa devera ler da entrada padrao do sistema a instˆancia no seguinte formato um inteiro n representando o numero de dıgitos dos fatores a serem multiplicados na linha seguinte o primeiro fator da multiplicacao um inteiro com n dıgitos e na proxima linha o segundo fator da multiplicacao outro inteiro com n dıgitos 4 1234 5678 A saıda deve ser APENAS o valor resultante da multiplicacao desses dois inteiros calculado utilizando o Algoritmo de Karatsuba 7006652 2