เครื่องคำนวณการประมาณค่าแบบ Chebyshev

 (stuffmatic.com)
2 คะแนน โดย GN⁺ 2024-10-06 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Chebyshev approximation calculator เป็นเครื่องมือที่สร้าง โค้ดสำหรับประมาณค่าฟังก์ชันทางคณิตศาสตร์ บนเว็บ
  • ผู้ใช้สามารถระบุ ฟังก์ชันและช่วง รวมถึงจำนวนพจน์ ที่ต้องการประมาณค่าได้ด้วย f(x), x min, x max, Terms
  • มีขั้นตอนให้ตรวจสอบหรือปรับขอบเขตของช่วงและ ค่าค่าสัมประสิทธิ์ ผ่านตัวเลือก Match x min x max และพื้นที่ Coefficients
  • ในพื้นที่ Generated code ผลลัพธ์การคำนวณจะแสดงในรูปแบบโค้ด และในหน้าจอตัวอย่างมีค่าสัมประสิทธิ์ตั้งแต่ c0 ถึง c10
  • มีการเชื่อมโยงไปยัง GitHub repository ทำให้สามารถตรวจสอบโค้ดการทำงานของเครื่องมือเว็บนี้ได้โดยตรง

ตัวสร้างโค้ดการประมาณค่าแบบ 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 ด้วย

คลังโค้ด

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-10-06
ความคิดเห็นจาก Hacker News

  • เจ๋งดีครับ ราวปี 1974 ผมเคยเขียนฟังก์ชันคำนวณรากที่สองด้วย IBM 360 assembly แล้วได้รับค่าจ้าง
    ตอนนั้นเป็นปีสุดท้ายของปริญญาตรี และถูกขอให้ทำให้มีประสิทธิภาพที่สุดเท่าที่จะทำได้ ผมสเกลอินพุตให้อยู่ระหว่าง 0 กับ 1 แล้วใช้ การประมาณแบบ Chebyshev สำหรับค่าประมาณเริ่มต้น จากนั้นใช้วิธีของ Newton แบบคลี่ลูปวนซ้ำ 2 หรือ 3 รอบเพื่อหาคำตอบ นั่นเป็นรายได้ครั้งแรกที่ได้จากการเขียนโค้ด

    • ชอบเรื่องแบบนี้จัง ยังจำได้อยู่เลยว่าตอนเรียนวิชา numerical analysis ครั้งแรก ผมตาสว่างเมื่อได้เห็นศักยภาพของการคำนวณเป็นครั้งแรก

  • ทำได้ดีมากจริงๆ ผมทึ่งกับประสิทธิภาพของการประมาณแบบนี้ และเข้าใจมากขึ้นว่าทำไมการ implement ฟังก์ชันตรีโกณมิติหรือฟังก์ชันคณิตศาสตร์อื่นๆ บน คอมพิวเตอร์ 8 บิต ถึงทำกันแบบนั้น
    มีเอกสารต้นฉบับดีๆ จาก BBC Research Department ปี 1969 ที่อธิบายว่าทำไมแนวทางนี้ถึงยอดเยี่ยม: https://downloads.bbc.co.uk/rd/pubs/reports/1969-10.pdf
    ถ้าเคยเจอแค่ การประมาณแบบ Taylor ตอนแรกมันอาจดูเหมือนเวทมนตร์นิดๆ

    • ใช่เลย ทั้งในแง่คณิตศาสตร์ และในแง่ที่ท้ายที่สุดมันเหลือเป็นโค้ดแค่ไม่กี่บรรทัด ก็ดูเหมือนเวทมนตร์อยู่พอสมควร

  • เมื่อก่อนผมเคยได้ผลลัพธ์ดีๆ จาก Sollya: https://www.sollya.org/
    แต่ถึงผลลัพธ์จะดี ตัวซอฟต์แวร์เองใช้ค่อนข้างยุ่งยาก

    • Sollya น่าจะเป็นหนึ่งในเครื่องมือสมัยใหม่ที่ดีที่สุดสำหรับงานแบบนี้ ภายในมันทำ การประมาณแบบ Remez แล้ว quantize เป็น floating point ด้วย LLL ไม่ได้ใช้ Chebyshev โดยตรง

  • ถ้าประมาณ Math.sin(x)/x หรือก็คือ ฟังก์ชัน sinc บนช่วง [-3,3] ด้วย 7 พจน์ ค่าสัมประสิทธิ์ c0...c6 ทั้งหมดจะกลายเป็น NaN นี่เป็นบั๊กไหม?
    วิธีแก้ชั่วคราวคือบังคับให้เป็น 1.0 ไปเลยเมื่อ x ใกล้ 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)) เพื่อหาสัมประสิทธิ์ Chebyshev และถ้าหนึ่งในจุดนั้นเป็น 0 พอดี ก็จะคำนวณ Math.sin(0)/0 จนได้ NaN
      วิธีเลี่ยงอีกแบบคือใช้ช่วงที่ไม่สมมาตรเล็กน้อย เช่น [-3,+3.0000001]
    • ปัญหาตรงนี้คือสูตรแรกไม่ได้ถูกนิยามอย่างดีที่ x=0 และโค้ดประมาณค่าน่าจะสะดุดตรงนั้น โค้ดน่าเสียดายหน่อยนะ
    • ใช่แล้ว เป็น บั๊ก ฟังก์ชันควรถูกนิยามที่ทุก Chebyshev node ไม่อย่างนั้นแอปควรแสดงข้อผิดพลาด อย่างที่คุณเจอ ตอนนี้เลี่ยงได้ง่ายอยู่

  • พหุนาม Chebyshev ทรงพลังและอเนกประสงค์มากในการประมาณค่า จนคนคิดว่ามันดีเกินจริงเหมือนหลอกลวง แล้วกลับไม่ใช้มัน
    วิธีแรกที่ควรลองควรเป็น Chebyshev ส่วน neural network ควรเป็นทางเลือกสุดท้าย

  • ยอดเยี่ยมเลย ช่วงหลังผมอยากทำอะไรแบบนี้พอดี แต่กลับพบว่ายากอย่างน่าประหลาดใจที่จะหาโค้ดสำหรับคำนวณการประมาณ
    เลยบุ๊กมาร์กไว้ เผื่อครั้งหน้าต้องประมาณฟังก์ชันให้เร็ว

    • ผมเองก็แปลกใจเหมือนกันว่าการหา โค้ดประมาณแบบ Chebyshev ที่ใช้งานได้จริงนั้นยากแค่ไหน หวังว่าโปรเจกต์นี้จะเปลี่ยนเรื่องนั้นได้

  • Chebyshev เหมือน มนตร์ดำ เลย ถึงจะเคยเห็นขั้นตอนการ derive ในคลาสระดับบัณฑิตศึกษาแล้วก็ยังรู้สึกแบบนั้น

  • ต้องพูดถึง Chebfun ของ Nick Trefethen และคณะด้วย เครื่องมือนี้ขยายแนวคิดนี้ออกไปแทบทุกทิศทางที่นึกออก
    Chebfuns มองได้ว่าเป็นสิ่งคู่กันของฟังก์ชัน คล้ายกับที่ floating point number เป็นตัวแทนของจำนวนจริงทางคณิตศาสตร์ เป็นซอฟต์แวร์ที่น่าประทับใจจริงๆ
    https://www.chebfun.org

    • เห็นด้วย วิธีการสายนี้ทรงพลังและเร็วมาก เทคนิคที่อิง Chebyshev และ ultraspherical functions สามารถประมาณฟังก์ชันส่วนใหญ่ได้ถึงระดับ machine precision อย่างรวดเร็วมาก และหลังจากนั้นก็จัดการกับ representation นั้นได้ง่ายขึ้น
      ทำให้ทำอะไรได้หลากหลาย เช่น หาคำตอบของ differential-algebraic equations ที่ระดับ machine precision หรือหาค่าต่ำสุด/สูงสุดทั่วทั้งโดเมนของฟังก์ชันหนึ่งมิติ
      เท่าที่รู้ตอนนี้เขาใช้อัลกอริทึมอื่นแล้ว แต่วิธีพื้นฐานที่ Chebfun เคยใช้ดูได้ในบทที่ 6 ของหนังสือ Spectral Methods in Matlab ของ Trefethen ส่วนวิธีสมัยใหม่ที่ใช้ ultraspherical functions อยู่ในบทความ SIAM Review ของ Olver และ Townsend เรื่อง A Fast and Well-Conditioned Spectral Method

  • มีเรื่องสงสัย ไม่รู้ถามตรงนี้ได้ไหม เมื่อก่อนผมเคยดูวิดีโอที่บอกว่า Nintendo 64 ไม่มีความสามารถพอจะคำนวณ ฟังก์ชัน sine เลยใช้ lookup table ตั้งแต่ 0 ถึง 2π และยังมีเทคนิคฉลาดๆ เพื่อลดขนาดตารางด้วย
    เป็นไปได้ไหมที่จะเทรน neural network แล้วเก็บ weights หรือสร้างฟังก์ชันแล้วเก็บ coefficients เพื่อคำนวณ sine/cosine?

    • neural network มักใช้ฟังก์ชันตรีโกณมิติภายในอยู่บ่อยๆ ดังนั้นจะต้องใช้การคำนวณมากเกินจำเป็นมาก
      ถ้ายังเหลือ CPU cycles นิดหน่อย อาจใช้ การประมาณแบบไฮบริด โดยเอาค่า lookup table แบบห่างๆ เป็นค่าประมาณเริ่มต้น แล้ววนซ้ำเทคนิค numerical approximation สักสองสามครั้ง หรือไม่ก็เก็บเฉพาะ coefficients ต้นๆ ไม่กี่ตัวของ polynomial approximation แบบในโพสต์ต้นทาง
    • ถ้ายังไม่คุ้น ลองดู CORDIC ก็ดีครับ เมื่อก่อนเป็นทริกคำนวณตรีโกณมิติที่พบได้ทั่วไป และทุกวันนี้ก็ยังใช้ใน embedded อยู่บ้าง
      neural network อาจมีประโยชน์เมื่อคุณมีตัวอย่างของฟังก์ชันบางอย่าง แต่ไม่รู้จะประมาณมันอย่างไร ทว่ากรณีนี้ไม่ใช่แบบนั้น
    • แน่นอนว่าการเทรน neural network ให้คำนวณฟังก์ชันใดๆ ก็เป็นไปได้ แต่สำหรับฟังก์ชันที่รู้จักดีอย่าง sine นั้นไม่สมเหตุสมผลเลย
      neural network เป็นทางออกที่ยอดเยี่ยมเมื่อต้องประเมินสิ่งที่วิเคราะห์ทางคณิตศาสตร์ได้ไม่ง่าย แต่เทคนิคที่รู้จักกันดีสำหรับคำนวณและประมาณฟังก์ชันตรีโกณมิติมีอยู่มากมายแล้ว
      การเทรน neural network เพื่อคำนวณ sine ก็เหมือนเวอร์ชันคณิตศาสตร์ของการใช้ LLM เพื่อกลับสตริง ทำได้ก็จริง แต่เป็นไอเดียที่จะนึกถึงก็ต่อเมื่อไม่รู้ว่าปัญหานี้แก้ได้โดยตรงในสาระสำคัญมากกว่า
      ก่อนใช้ เทคนิค AI/ML ควรตรวจดูเสมอว่านักคณิตศาสตร์มีวิธีแก้อยู่แล้วหรือไม่ ทุกวันนี้มีความเป็นไปได้สูงที่คนจำนวนมากกำลังทุ่มแรงกับการเอา AI/ML ไปแปะกับปัญหาที่นักพัฒนาแค่ไม่รู้ว่าแท้จริงแล้วมีวิธีแก้ที่เป็นที่รู้จัก มีประสิทธิภาพ และแม้แต่เหมาะที่สุดอยู่แล้ว
    • neural network โดยแก่นแล้วคือ การ fit เส้นโค้ง ดังนั้นทำได้ วิดีโอนี้อาจช่วยได้: https://www.youtube.com/watch?v=FBpPjjhJGhk But what is a neural network REALLY?
      จุดแข็งหลักของ neural network จะเห็นชัดเมื่อมีอินพุตจำนวนมาก ไม่ใช่แค่ไม่กี่ตัว สำหรับกรณีง่ายๆ อย่าง sin(x) ก็มีวิธีอื่นอย่างเครื่องมือที่โพสต์นี้พูดถึง
    • เทคนิคประหยัดที่ใช้กันทั่วไปคือเก็บตารางแค่ตั้งแต่ 0 ถึง π/2 แล้วใช้ บิตดัชนีเพิ่มอีก 2 บิต เพื่อสร้างอีกสาม quadrant ที่เหลือ

  • เจ๋งมาก ผมเกิดอยากลองเล่นดูว่าทำฟังก์ชันที่ประมาณได้ไม่ดีขึ้นมาได้เร็วแค่ไหน
    จนถึงตอนนี้ Math.cos(x * Math.exp(Math.cos(x * x))) ทำได้ดีที่สุด มีการ compose หลายชั้นจนเกิดการสั่นเร็วและความชันสูง ทำให้ Chebyshev ประมาณได้ยาก