[Algorithm] Math - Liu Hui's π Algorithm - 하고싶은거하는

Liu Hui의 π 알고리즘이란?

Liu Hui의 π 알고리즘은 기원후 263년경 중국 수학자 Liu Hui가 개발한 π(파이)의 값을 계산하는 고대 알고리즘입니다. 이 방법은 아르키메데스가 제안한 내접 다각형 방법에 기초하고 있으며, Liu Hui는 이를 개선하고 확장했습니다.

이 알고리즘의 핵심 아이디어는 점점 더 많은 변을 가진 다각형을 원 안에 내접시켜, 다각형의 둘레가 원의 둘레에 점점 가까워지게 하는 것입니다. 변의 개수가 증가할수록 다각형은 원과 비슷한 형태가 되어 그 둘레는 원의 둘레에 가까워지며, 따라서 π의 값도 더 정확해집니다.

Liu Hui는 처음에 원 안에 내접하는 육각형부터 시작하여 둘레를 계산했습니다. 이후 변의 개수를 6에서 12, 24, 48 등으로 두 배씩 늘리며 π의 값을 점점 더 정확하게 계산했습니다.

Liu Hui 알고리즘의 단계

내접 다각형(예: 육각형)으로 시작합니다.
각 반복마다 변의 개수를 두 배로 늘립니다(예: 6 -> 12 -> 24 -> 48 등).
다각형의 둘레를 계산합니다.
이 둘레를 사용하여 π 값을 근사합니다. 변의 개수가 증가할수록 더 정확한 값을 얻을 수 있습니다.

수식으로 표현하면: $ \pi \approx \frac{P}{2r} $ 여기서 $P$는 다각형의 둘레이고, $r$은 원의 반지름입니다.

Liu Hui의 π 알고리즘의 사용 사례

기하학: 다각형과 원의 관계를 기하학적으로 이해하는 데 도움을 줍니다.
수학사: π 계산의 발전 과정에서 중요한 역사적 의미를 가지고 있습니다.
수치 해석: 반복적인 근사 방법을 보여주며, 이는 현대 수치 해석에서도 널리 사용됩니다.
컴퓨터 그래픽스: 곡선을 다각형으로 근사하는 방법은 현대 컴퓨터 그래픽스에서도 표준 기법입니다.

JavaScript로 구현한 Liu Hui의 π 알고리즘

function liuHuiPi(steps) {
  let sides = 6; // 육각형으로 시작
  let sideLength = 1; // 반지름이 1일 때 육각형의 변 길이

  for (let i = 0; i < steps; i++) {
    let halfSide = Math.sqrt(1 - Math.pow(sideLength / 2, 2));
    sideLength = Math.sqrt(
      Math.pow(sideLength / 2, 2) + Math.pow(1 - halfSide, 2)
    );
    sides *= 2; // 변의 개수를 두 배로 늘림
  }

  // 다각형의 둘레
  const perimeter = sides * sideLength;

  // π의 근사는 둘레를 지름(2 * 반지름)으로 나눈 값
  return perimeter / 2;
}

console.log(liuHuiPi(10)); // 더 많은 반복을 할수록 더 정확한 값

Rust로 구현한 Liu Hui의 π 알고리즘

fn liu_hui_pi(steps: u32) -> f64 {
    let mut sides = 6.0; // 육각형으로 시작
    let mut side_length = 1.0; // 반지름이 1일 때 초기 육각형의 변 길이

    for _ in 0..steps {
        let half_side = (1.0 - (side_length / 2.0).powi(2)).sqrt();
        side_length = ((side_length / 2.0).powi(2) + (1.0 - half_side).powi(2)).sqrt();
        sides *= 2.0; // 변의 개수를 두 배로 늘림
    }

    // 다각형의 둘레
    let perimeter = sides * side_length;

    // π의 근사는 둘레를 지름(2 * 반지름)으로 나눈 값
    perimeter / 2.0
}

fn main() {
    println!("{}", liu_hui_pi(10)); // 더 많은 반복을 할수록 더 정확한 값
}

요약:

Liu Hui의 π 알고리즘은 내접하는 다각형을 이용해 π를 근사하는 반복적 기하학적 방법입니다. 각 반복에서 변의 개수를 늘리면 다각형의 둘레가 원의 둘레에 가까워지고, π의 값도 더 정확해집니다. 이 알고리즘은 역사적으로 중요하며, 현대 수치 해석의 개념을 보여줍니다. JavaScript와 Rust로 π 근사를 쉽게 구현할 수 있습니다.

What is Liu Hui’s π Algorithm?

Liu Hui’s π algorithm is an ancient Chinese algorithm developed by mathematician Liu Hui around 263 AD to calculate the value of π (pi). The method is based on the inscribed polygon method, originally proposed by Archimedes, but Liu Hui refined and extended it.

The idea behind the algorithm is to approximate the circumference of a circle by using polygons with an increasing number of sides inscribed within the circle. As the number of sides increases, the polygon becomes closer to the shape of the circle, and its perimeter approaches the circumference, which is proportional to π.

Liu Hui started with a hexagon inscribed inside a circle and calculated the perimeter. Then, he doubled the number of sides of the polygon (e.g., from 6 to 12, 24, 48, etc.), each time getting a better approximation of the circumference of the circle, and thus, π.

Steps in Liu Hui’s Algorithm

Begin with an inscribed polygon, such as a hexagon.
Double the number of sides at each iteration (from 6 to 12, 24, 48, and so on).
Calculate the perimeter of the polygon.
Use the perimeter to approximate the value of π. As the number of sides increases, the approximation becomes more accurate.

The relationship is expressed as: $ \pi \approx \frac{P}{2r} $ Where $P$ is the perimeter of the polygon, and $r$ is the radius of the circle.

Applications of Liu Hui’s π Algorithm

Geometry: The algorithm gives a geometric understanding of the relationship between polygons and circles.
History of Mathematics: Liu Hui’s method is historically significant in the development of π calculations.
Numerical Methods: This method demonstrates iterative approximation, a concept widely used in numerical analysis today.
Computer Graphics: In modern times, polygon approximation of curves is a standard technique in computer graphics.

JavaScript Implementation of Liu Hui’s π Algorithm

function liuHuiPi(steps) {
  let sides = 6; // Start with a hexagon
  let sideLength = 1; // Assume the radius is 1, the side length of hexagon is 1

  for (let i = 0; i < steps; i++) {
    let halfSide = Math.sqrt(1 - Math.pow(sideLength / 2, 2));
    sideLength = Math.sqrt(
      Math.pow(sideLength / 2, 2) + Math.pow(1 - halfSide, 2)
    );
    sides *= 2; // Double the number of sides
  }

  // Perimeter of the polygon
  const perimeter = sides * sideLength;

  // Pi approximation is perimeter divided by the diameter (2 * radius)
  return perimeter / 2;
}

console.log(liuHuiPi(10)); // Increase the steps for better approximation

Rust Implementation of Liu Hui’s π Algorithm

fn liu_hui_pi(steps: u32) -> f64 {
    let mut sides = 6.0; // Start with a hexagon
    let mut side_length = 1.0; // Assume the radius is 1, initial side length of hexagon

    for _ in 0..steps {
        let half_side = (1.0 - (side_length / 2.0).powi(2)).sqrt();
        side_length = ((side_length / 2.0).powi(2) + (1.0 - half_side).powi(2)).sqrt();
        sides *= 2.0; // Double the number of sides
    }

    // Perimeter of the polygon
    let perimeter = sides * side_length;

    // Pi approximation is perimeter divided by the diameter (2 * radius)
    perimeter / 2.0
}

fn main() {
    println!("{}", liu_hui_pi(10)); // Increase the steps for a better approximation
}

Summary:

Liu Hui’s π Algorithm provides an iterative geometric approach to approximate π by inscribing polygons inside a circle and increasing the number of sides. Each iteration gets a closer approximation of π. The algorithm is historically important and demonstrates principles used in modern numerical methods. Both JavaScript and Rust can efficiently implement this approach for approximating π.

[Algorithm] Math - Liu Hui's π Algorithm

수학 리우 후이 π 알고리즘