Chebyshev 근사 계산기

 (stuffmatic.com)
2P by GN⁺ | ★ favorite | 댓글 1개
  • Chebyshev approximation calculator는 수학 함수 근사 코드를 웹에서 생성해 주는 도구임
  • 사용자는 f(x), x min, x max, Terms로 근사할 함수와 구간, 항 수를 지정할 수 있음
  • Match x min x max 옵션과 Coefficients 영역을 통해 구간 경계와 계수 값을 확인하거나 조정하는 흐름을 제공함
  • Generated code 영역에는 계산 결과가 코드 형태로 표시되며, 예시 화면에는 c0부터 c10까지의 계수가 보임
  • GitHub 저장소가 연결되어 있어 웹 도구의 구현 코드를 직접 확인할 수 있음

Chebyshev 근사 코드 생성기

  • Chebyshev approximation calculator는 수학 함수를 효율적으로 근사하기 위한 코드를 생성함
  • 웹 UI에서 근사 조건을 입력함
    • f(x): 근사할 함수
    • x min: 구간 최솟값
    • x max: 구간 최댓값
    • Terms: 사용할 항 수
    • Match x min x max: 구간 경계와 관련된 옵션

계수 확인과 생성 코드

  • 화면은 Coefficients 영역과 Generated code 영역으로 나뉨
  • 예시로 표시된 계수는 c0부터 c10까지 확인할 수 있음
    • c0 = 0.16793649417016518
    • c1 = -0.12411164956092625
    • c2 = -0.09756341588422193
    • c3 = 0.1800765790518846
    • c4 = -0.06972963647223016
    • c5 = -0.09250127939333941
    • c6 = 0.18076946080324185
    • c7 = 0.15990613621816677
    • c8 = -0.028659588693985123
    • c9 = -0.09494966104347571
    • c10 = -0.04980429834982578
  • 화면에는 c11부터 c39까지의 계수 항목도 표시됨

코드 저장소

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 멋지네요. 1974년쯤 IBM 360 어셈블리로 제곱근을 계산하는 함수를 작성하고 돈을 받은 적이 있음
    학부 마지막 해였고, 최대한 효율적으로 만들라는 요청을 받았음. 입력을 0과 1 사이로 스케일링한 뒤 초기 추정에는 체비쇼프 근사를 쓰고, 뉴턴 방법을 펼친 반복 2번인지 3번인지 적용해 해를 구했음. 코드를 써서 받은 첫 수입이었음

    • 이런 얘기 좋음. 수치해석 첫 수업에서 계산의 잠재력을 처음 실감하며 눈이 확 트였던 기억이 아직도 남아 있음

  • 정말 잘 만들었음. 이런 근사가 얼마나 효율적인지에 매료됐고, 8비트 컴퓨터에서 삼각함수나 다른 수학 함수 구현이 왜 그런 식이었는지도 많이 이해됐음
    1969년 BBC Research Department가 왜 이런 방식이 훌륭한지 다룬 멋진 원문 문서도 있음: https://downloads.bbc.co.uk/rd/pubs/reports/1969-10.pdf
    테일러 근사만 접해봤다면 처음에는 약간 마법처럼 보일 수 있음

    • 맞음. 수학적인 면도 그렇고, 실제로는 몇 줄의 코드로 귀결된다는 점도 꽤 마법처럼 느껴짐

  • 예전에 Sollya로 좋은 결과를 얻은 적이 있음: https://www.sollya.org/
    단, 결과는 좋았지만 소프트웨어 자체는 쓰기 좀 번거로움

    • Sollya가 아마 이런 작업을 위한 현대적인 도구 중 최고일 것임. 내부적으로는 Remez 근사를 한 뒤 LLL로 부동소수점에 양자화하며, 체비쇼프를 직접 쓰지는 않음

  • Math.sin(x)/x, 즉 sinc 함수를 [-3,3] 구간에서 7개 항으로 근사하면 계수 c0...c6가 전부 NaN이 됨. 버그인가?
    임시 해결로 x가 0에 가까운 경우를 그냥 1.0으로 강제했음
    if(Math.abs(x) > 1e-8 ){ Math.sin(x)/x } else { 1.0 }

    • 정확히 버그라고 보긴 어려움. 코드는 아마 체비쇼프 계수를 구하려고 x_j = (xmin) + (xmax - xmin)/2(1 + cos(pi[0..j-1]/(j-1)) 같은 격자점에서 함수를 평가할 텐데, 그중 하나가 정확히 0이면 Math.sin(0)/0을 계산하게 되어 NaN이 나옴
      다른 우회법으로는 [-3,+3.0000001]처럼 살짝 비대칭인 범위를 쓰는 방법이 있음
    • 여기서 문제는 첫 식이 x=0에서 잘 정의되지 않았고, 근사 코드가 거기서 넘어진 것 같음. 코드가 좀 아쉽네요
    • 맞음, 버그임. 함수가 모든 체비쇼프 노드에서 정의되지 않으면 앱이 오류를 보여줘야 함. 이미 찾은 것처럼 지금은 쉽게 우회 가능함

  • 체비쇼프 다항식은 근사에서 너무 강력하고 다재다능해서, 사람들이 너무 좋아서 사기 같다고 생각하고 오히려 쓰지 않음
    첫 번째로 시도할 방법은 체비쇼프여야 함. 신경망은 최후의 수단으로 써야 함

  • 훌륭함. 최근에 이런 걸 하고 싶었는데, 근사를 계산하는 코드를 찾기가 놀랄 만큼 어려웠음
    다음에 함수를 빠르게 근사해야 할 때 쓰려고 북마크해둠

    • 실제로 동작하는 체비쇼프 근사 코드를 찾기가 나도 놀랄 만큼 어려웠음. 이 프로젝트가 그걸 바꿔주면 좋겠음

  • 체비쇼프는 흑마법 같음. 대학원 수업에서 유도 과정을 봤는데도 그렇게 느껴짐

  • Nick Trefethen 등의 Chebfun도 꼭 언급해야 함. 이 내용을 생각할 수 있는 거의 모든 방향으로 확장한 도구임
    Chebfuns는 실제 수학적 수에 대한 부동소수점 수처럼, 함수에 대한 대응물이라고 볼 수 있음. 정말 인상적인 소프트웨어임
    https://www.chebfun.org

    • 동의함. 그쪽 방법들은 매우 강력하고 빠름. 체비쇼프와 초구면 함수 기반 기법을 쓰면 대부분의 함수를 매우 빠르게 기계 정밀도 수준으로 근사할 수 있고, 이후 그 표현을 더 쉽게 조작할 수 있음
      덕분에 미분대수방정식 해를 기계 정밀도로 찾거나 1차원 함수의 전역 최솟값/최댓값을 찾는 등 다양한 방법이 가능해짐
      지금은 다른 알고리즘을 쓰는 것으로 알지만, Chebfun이 예전에 쓰던 기본 방법론은 Trefethen의 책 Spectral Methods in Matlab 6장에서 볼 수 있음. 초구면 함수를 쓰는 최신 방법론은 Olver와 Townsend의 SIAM Review 논문 A Fast and Well-Conditioned Spectral Method에 나와 있음

  • 궁금한 게 있는데 여기서 물어봐도 될지 모르겠음. 예전에 Nintendo 64가 사인 함수를 계산할 능력이 없어서 0부터 2π까지의 조회표를 썼고, 표 크기를 줄이는 영리한 기법도 썼다는 영상을 봤음
    신경망을 학습시켜 가중치를 저장하거나, 함수를 만들어 계수를 저장해서 사인·코사인을 계산하는 것도 가능했을까?

    • 신경망은 내부적으로 삼각함수를 쓰는 경우가 많아서, 필요한 것보다 훨씬 많은 계산이 들어갈 것임
      CPU 사이클이 조금 남는다면, 성긴 조회표 값을 초기 추정으로 삼고 수치 근사 기법을 몇 번 반복하는 하이브리드 근사를 쓸 수 있음. 아니면 원글처럼 다항식 근사의 앞쪽 계수 몇 개만 저장하면 됨
    • 익숙하지 않다면 CORDIC을 살펴보면 좋음. 예전에는 흔한 삼각함수 꼼수였고, 지금도 임베디드 쪽에서는 어느 정도 쓰임
      신경망은 어떤 함수의 샘플은 있지만 어떻게 근사할지 모를 때 유용할 수 있는데, 여기서는 그런 경우가 아님
    • 어떤 함수든 계산하도록 신경망을 학습시키는 건 당연히 가능하지만, 사인처럼 잘 알려진 함수에는 전혀 말이 안 됨
      신경망은 수학적으로 분석하기 쉽지 않은 대상을 평가해야 할 때 훌륭한 해법이지만, 삼각함수를 계산하고 근사하는 알려진 기법은 이미 많음
      사인을 계산하려고 신경망을 학습시키는 건 문자열 뒤집기에 LLM을 쓰는 수학 버전 같음. 할 수는 있지만, 더 직접적인 접근으로 본질적으로 풀리는 문제라는 걸 모를 때나 떠올릴 발상임
      AI/ML 기법을 쓰기 전에 수학자들이 이미 해법을 갖고 있는지 찾아볼 가치는 항상 있음. 요즘은 개발자가 모를 뿐 이미 알려지고 효율적이며 심지어 최적인 해법이 있는 문제에 AI/ML을 붙이는 데 많은 노력이 쓰이고 있을 가능성이 큼
    • 신경망은 본질적으로 곡선 맞춤이니 가능은 함. 이 영상이 도움이 될 수 있음: https://www.youtube.com/watch?v=FBpPjjhJGhk But what is a neural network REALLY?
      신경망의 주된 강점은 입력이 몇 개가 아니라 아주 많을 때 드러남. sin(x)처럼 단순한 경우에는 여기 올라온 도구 같은 다른 방법들이 있음
    • 보통 쓰는 절약 기법은 0부터 π/2까지만 표로 저장하고, 추가 인덱스 비트 2개로 나머지 세 사분면을 생성하는 방식임

  • 아주 멋짐. 장난기가 발동해서 얼마나 빨리 잘 근사되지 않는 함수를 만들 수 있는지 보고 싶었음
    지금까지는 Math.cos(x * Math.exp(Math.cos(x * x)))가 제일 나았음. 합성이 많이 들어가서 빠른 진동과 가파른 기울기가 생기고, 체비쇼프로 쉽게 근사하기 어려워짐

답변달기