Module numbers 

Sonlar bilan ishlash algoritmlari

Darslik: 02-numbers/

Bu modul “matematik” algoritmlarni yig’adi: EKUB/EKUK, tub sonlar, modul arifmetikasi, Fibonachchi va bit sehrlari.

Vazifa	Sodda yechim	Bu yerdagi yechim
EKUB	O(min(a,b))	gcd — O(log min(a,b))
x tubmi?	O(x)	is_prime — O(√x)
1..n tub sonlar	O(n√n)	sieve_of_eratosthenes — O(n log log n)
aⁿ	O(n)	fast_pow — O(log n)
n-Fibonachchi	O(2ⁿ) rekursiya	fibonacci — O(n) / fibonacci_fast — O(log n)

Functions

count_ones

Sonda nechta 1 biti bor (population count) — Brian Kernighan usuli.

digit_sum

Raqamlar yig’indisi.

digits

Sonning raqamlari (eng kattasidan kichigiga qarab).

extended_gcd

Kengaytirilgan Evklid algoritmi: (g, x, y) shundayki a·x + b·y = g = gcd(a, b).

factorial

n! — faktorial (iterativ, overflowga xavfsiz).

fast_pow

a ning n -darajasi — tez darajaga ko’tarish (binary exponentiation).

fibonacci

n -Fibonachchi soni — iterativ, O(n).

fibonacci_fast

n -Fibonachchi soni — O(log n) (“fast doubling”).

gcd

Eng katta umumiy bo’luvchi (EKUB / GCD) — Evklid algoritmi.

is_power_of_two

n ikkining darajasimi? (1, 2, 4, 8, …)

is_prime

n tub sonmi? — 6k±1 optimallashtirishli sinov bo’linishi.

lcm

Eng kichik umumiy karrali (EKUK / LCM).

lowest_set_bit

Eng past 1 bitni ajratib oladi: n & (-n).

mod_inverse

a ning m moduli bo’yicha teskarisi: a · x ≡ 1 (mod m).

mod_pow

(a^n) mod m — modul bo’yicha tez darajaga ko’tarish.

prime_factors

Sonni tub ko’paytuvchilarga ajratadi: (tub_son, daraja) juftliklari.

reverse_number

Sonni teskari o’girish: 1234 → 4321.

sieve_of_eratosthenes

Eratosfen g’alviri — n gacha bo’lgan barcha tub sonlar.

smallest_prime_factors

Har bir son uchun uning eng kichik tub bo’luvchisi (SPF) jadvali.

subsets_of_mask

Bitmaskning barcha qism to’plamlari (o’zi va bo’sh to’plam bilan birga).

swap_xor

Uchinchi o’zgaruvchisiz almashtirish (XOR swap) — klassik hiyla.

to_base

Sonni base (2..=36) sanoq sistemasiga o’tkazadi.