การหารเชิงทดลอง

การหารเชิงทดลอง (อังกฤษ: trial division) เป็นขั้นตอนวิธีที่ทำความเข้าใจได้ง่าย เนื่องจากเป็นขั้นตอนวิธีที่ใช้วิธีการแบบบรู๊ทฟอร์ซ (brute-force) เพื่อช่วยในการแยกตัวประกอบของจำนวนเต็ม n โดยตรวจสอบว่ามีจำนวนเฉพาะใดๆที่มากกว่า 1 แต่น้อยกว่า n ที่สามารถหาร n ได้ลงตัว โดยวิธีนี้มักใช้กับการแยกตัวประกอบของจำนวนเต็มค่าน้อยๆ เนื่องจากประสิทธิภาพเชิงเวลาค่อนข้างช้า

คำอธิบาย

การหารเชิงทดลองนั้น ใช้หลักของการหาขอบเขตล่างและขอบเขตบน(lower bound&upper bound)เข้ามาช่วย กำหนดให้ จำนวนเต็ม n= s×t และ s ≤ t เราจะทำการตรวจสอบว่ามี s | n (หมายถึง s หาร n ได้ลงตัว) สำหรับจำนวน s = {2, ..., √n} โดยขอบเขตบน คือ s ≤ √n นั้น มีทฤษฎีดังนี้

ทฤษฎี : ตัวประกอบเฉพาะของจำนวนเต็มใดๆ จะต้องมีค่าน้อยกว่าหรือเท่ากับรากที่สองของจำนวนเต็มนั้นๆ

บทพิสูจน์ : สมมุติให้ s > √n ดังนั้น t ≥ s > √n เป็นผลให้ n < s×t ทำให้ขัดแย้งกับข้อเท็จจริง n = s×t เพราะฉะนั้น s ≤ N

ตัวอย่างที่1 : ให้จำนวนเต็มบวก n มีค่าเท่ากับ 7399 สามารถแสดงขั้นตอนวิธีการทำได้ดังนี้

1. ทดลองนำจำนวนเฉพาะ 2,3,5 มาหารพบว่า ไม่ใช่ตัวประกอบของ n (หาร n ไม่ลงตัว)
2. ทดลองนำจำนวนเฉพาะ 7 พบว่า 7 เป็นตัวประกอบของ n โดย n/7 = 1057
3. จากนั้นลองนำ 7 มาหารซ้ำอีกครั้ง พบว่า 7 เป็นตัวประกอบของ 1057 ทำให้ 1057/7 = 151
4. ลองนำ 7 มาหารอีกครั้ง พบว่าหารไม่ลงตัว ดังนั้น 7 ไม่ใช่ตัวประกอบของ 151
5. เลื่อนไปที่จำนวนเฉพาะตัวถัดไปคือ 11 พบว่าหารไม่ลงตัว ดังนั้น 11 ไม่ใช่ตัวประกอบของ 151
6. เมื่อเลื่อนไปที่จำนวนเฉพาะตัวถัดไปจาก 11 คือ 13 จะพบว่าไม่สามารถคิดต่อได้ เนื่องจาก 13 มีค่ามากกว่ารากที่สองของ 151 ซึ่งคือ 12.288
   

เพราะฉะนั้น ตัวประกอบของ 7399 คือ 7×7×151

ตัวอย่างที่2 : ให้จำนวนเต็มบวก n มีค่าเท่ากับ 491 สามารถแสดงขั้นตอนวิธีการทำได้ดังนี้

1. ทดลองนำจำนวนเฉพาะ 2, 3,5...,19พบว่าไม่ใช่ตัวประกอบของn (หาร n ไม่ลงตัว)
2. เมื่อเลื่อนไปที่จำนวนเฉพาะตัวถัดไปจาก 19 คือ 23 จะพบว่าไม่สามารถคิดต่อได้ เนื่องจาก 23 มีค่ามากกว่ารากที่สองของ 491 ซึ่งคือ 22.158
   

เพราะฉะนั้น 491 ไม่มีจำนวนเฉพาะใดๆเป็นตัวประกอบ 491 จึงเป็นจำนวนเฉพาะ

รหัสเทียม

def trial_division(n):
    """Return a list of the prime factors for a natural number."""
    if n == 1: return [1]
    primes = prime_sieve(int(n**0.5) + 1)
    prime_factors = []
 
    for p in primes:
        if p*p > n: break
        while n % p == 0:
            prime_factors.append(p)
            n //= p
    if n > 1: prime_factors.append(n)
 
    return prime_factors

ประสิทธิภาพการทำงาน

ประสิทธิภาพเชิงเวลาของการหารเชิงทดลอง ในกรณีที่แย่ที่สุด คือ จำนวนเต็มที่ต้องการทดลองเป็นจำนวนเฉพาะ ในกรณีนี้จะใช้จำนวนเฉพาะตั้งแต่ 2 ถึง √n โดยต้องทำเป็นจำนวน 2√n / ln n ครั้ง ทำให้มีประสิทธิภาพเชิงเวลาเป็น O(√n / log n)

การใช้การหารเชิงทดลองเป็นวิธีที่รวดเร็วสำหรับการแยกตัวประกอบของจำนวนเต็มที่มีตัวประกอบน้อยๆ เนื่องจาก มีจำนวนเต็ม 50% ที่มี 2 เป็นตัวประกอบ, 33% ที่มี 3 เป็นตัวประกอบ, 88% ที่มีจำนวนเต็มที่มีค่าน้อยกว่า 100 เป็นตัวประกอบ และ 92% ที่มีจำนวนเต็มที่มีค่าน้อยกว่า 1000 เป็นตัวประกอบ ดังนั้นจึงคุ้มค่าที่จะเริ่มหาตัวประกอบจากจำนวนเฉพาะดังขั้นตอนวิธีนี้

การประยุกต์ใช้

การหารเชิงทดลองเป็นขั้นตอนวิธีที่ช่วยในการแยกตัวประกอบจำนวนเต็ม การหาตัวประกอบเฉพาะ และการหาตัวหารร่วมมาก

ดูเพิ่ม

ขั้นตอนวิธีที่เกี่ยวข้องกับการแยกตัวประกอบ อาทิ

• ขั้นตอนวิธีของชอร์
• ขั้นตอนวิธีโรห์ของพอลลาร์ด
• ตะแกรงของเอราทอสเทนีส
• การแยกตัวประกอบแบบออยเลอร์

อื่นๆ

ตัวอย่างการทำหารหารเชิงทดลองด้วนภาษาคอมพิวเตอร์ต่างๆ

• ภาษาซี
  

ตัวอย่างการเขียนภาษาซีแสดงการเขียนการหารเชิงทดลอง

• ภาษาจาวา

ตัวอย่างการเขียนภาษาจาวาแสดงการเขียนการหารเชิงทดลอง

อ้างอิง

• Carl Pomerance, Richard E. Crandall (2000), "Prime numbers: a computational perspective", Department of Mathematics, Dartmouth College .
• Cafiero, Franco., "Improving Trial Division: FIRST-DIGIT ANALYSIS",  .