2
2 개의 숫자 곱셈에 대해 가능한 가장 빠른 알고리즘을 작성하고 싶습니다. 각 숫자는 최대 1000000 자릿수이며 문자열에 포함되어 있습니다.문자열 (숫자 1000000 자리)에서 숫자 곱셈을 구현하는 가장 빠른 방법
누구나이 문제에 대해 이야기하고 싶습니까? 나는 정말로 속도 솔루션을 찾고있다.
A
답변
4
문자열을 숫자의 이진 표현으로 변환해야합니다. 그 후 내가 아는 가장 빠른 곱셈 알고리즘 중 하나는 Karatsuba's입니다.
+3
위키피디아의 기사에 따르면 Strassen의 알고리즘은 Karatsuba가 10k에서 40k 자리까지의 숫자에서 시작하는 것보다 뛰어나다. – michalburger1
0
그냥 파블로의 대답을 확장하려면 각 숫자가 10 진수 1000008 자릿수 인 것으로 가정합니다. 111112 9 자리 10 진수로 변환 할 수 있으며 각각 UInt32에 저장됩니다. 귀하의 곱셈 알고리즘을 수행하십시오. (두 개의 UInt32 섹션을 곱한 결과를 유지하려면 UInt64를 사용해야하므로 64 비트 시스템이 필요할 수 있습니다.) 그러면 기본 10을 기준으로 9^2 또는 9^log2 (3)의 속도가 향상됩니다 , 알고리즘에 따라 다릅니다.
관련 문제
- 1. 문자열 (1000000 자리)에서 number sqare root를 구현하는 가장 빠른 방법
- 2. 주어진 숫자 중에서 유일한 요소를 찾는 가장 빠른 방법
- 3. Python : 숫자 문자열 식별?
- 4. 숫자 형식 문자열 : 시간
- 5. 배열 키 (문자열 및 숫자)
- 6. 숫자 목록을 저장하고 검색하는 가장 좋은 방법
- 7. jquery로 숫자 (숫자)를 제어하는 방법
- 8. 문자열 형식에 숫자 먹으 렴을 선택하는 방법
- 9. 숫자 문자열 패딩에 대한 도움말
- 10. 문자열 형식 % (유효 숫자 포함)
- 11. 숫자 합성 형식을 사용하여 숫자 문자열 서식 지정
- 12. 숫자 집합에서 임의의 숫자 선택
- 13. 정규식 숫자
- 14. 복잡한 숫자 : 빠른 직교 - 극 변환
- 15. FTP에서 mktree를 구현하는 가장 빠른 방법
- 16. 숫자 속성에 액세스하는 방법?
- 17. PHP 숫자 조작
- 18. C에서 사전을 구현하는 빠른 방법
- 19. 알고리즘은 숫자
- 20. 문자열에서 숫자 문장을 찾는 방법
- 21. C# 정규식 정렬 문자와 숫자 문자열
- 22. 숫자 필드는`
- 23. 숫자 반올림
- 24. 큰 숫자 변환 문제
- 25. Objective-C에서 반올림 숫자
- 26. 숫자 키
- 27. Node.js를 구문 분석하는 숫자 내부 문자열
- 28. 이 문자열 값이 숫자 인 이유는 무엇입니까?
- 29. C++ 인라인 문자열 서식 및 숫자 변환
- 30. 숫자 델타를 생성하는 두 개의 문자열 비교
결과를 문자열로 나타내려면 답변을 저장하는 데 최대 1TB의 저장 공간이 필요하지 않습니까? – philcolbourn
@philcolbourn 제품에는 2 백만 자릿수 만 있습니다.). – michalburger1
@Paul 숫자에 A와 B 숫자를 곱하면 제품에 A * B 숫자가 아닌 A + B 숫자가 표시됩니다. 예를 들어, 1e10 * 1e10 = 1e20이 아닌 1e100을 곱하면됩니다. – michalburger1