Reeds-Sloane 알고리즘은 주어진 정수 수열의 최소 길이 선형 점화식을 찾는 알고리즘입니다. Berlekamp-Massey 알고리즘이 소수 모듈로에 대해서만 작동하는 것과 달리, Reeds-Sloane 알고리즘은 임의 모듈로에 대해 작동합니다. 내부적으로는 모듈로를 basm::math::factorize로 소인수분해한 뒤, 모듈로의 각 prime power에 대해 핵심 로직을 돌린 다음 중국인의 나머지 정리(CRT)를 이용해 결과를 병합하는 방식으로 작동합니다.
구현은 완료되었으나 할 일이 두 가지가 남아있습니다.
1) 테스트를 추가해야 합니다. 추가 완료되었습니다.
2) 현재 구현체 이름을 basm::math::linear_fit으로 하였는데, 유지하거나, basm::math::reeds_sloane으로 바꾸거나, 아니면 둘 다 제공하거나(이 경우는 하나가 다른 하나의 alias가 됨) 중에서 선택해야 합니다.basm::math::reeds_sloane으로 바꾸고, basm::math::linear_fit은 alias가 되도록 하였습니다.
Reeds-Sloane 알고리즘은 주어진 정수 수열의 최소 길이 선형 점화식을 찾는 알고리즘입니다. Berlekamp-Massey 알고리즘이 소수 모듈로에 대해서만 작동하는 것과 달리, Reeds-Sloane 알고리즘은 임의 모듈로에 대해 작동합니다. 내부적으로는 모듈로를
basm::math::factorize로 소인수분해한 뒤, 모듈로의 각 prime power에 대해 핵심 로직을 돌린 다음 중국인의 나머지 정리(CRT)를 이용해 결과를 병합하는 방식으로 작동합니다.알고리즘 논문 링크(PDF): http://neilsloane.com/doc/Me111.pdf
구현은 완료되었으나 할 일이 두 가지가 남아있습니다. 1)
테스트를 추가해야 합니다.추가 완료되었습니다. 2)현재 구현체 이름을basm::math::linear_fit으로 하였는데, 유지하거나,basm::math::reeds_sloane으로 바꾸거나, 아니면 둘 다 제공하거나(이 경우는 하나가 다른 하나의 alias가 됨) 중에서 선택해야 합니다.basm::math::reeds_sloane으로 바꾸고,basm::math::linear_fit은 alias가 되도록 하였습니다.