Hızlı Modüler Üs Alma
pow(a, b, m) ile üsleri hesaplayın.
Hızlı Modüler Üs Alma, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Üs Alma Problemi
Çoğu zaman bir sayıyı devasa bir üsse yükseltmeniz ve bunu bir modül altında yapmanız gerekir. Her çarpanı tek tek çarpmak çok fazla adım gerektirir. ⚡
Naif Yöntem Çok Yavaş
b kez çarpma yapan bir döngü O(b) adımda çalışır. Üs bir milyara yaklaştığında, işlem tamamlanmadan önce zaman sınırını aşar.
for _ in range(b): r = r * a % MODDaha Hızlı İlerlemek İçin Kare Alın
İşin püf noktası kare alma işlemidir: a'nın 8. kuvvetini, a'nın karesini üç kez alarak elde edebilirsiniz. Her kare alma işleminde üs iki katına çıkar; böylece büyük kuvvetlere birkaç adımda ulaşırsınız.
Üssü İkilik Olarak Okuyun
Her üs, ikinin kuvvetlerinin toplamı olarak yazılabilir; bu onun ikilik gösterimidir. Böylece yalnızca biti 1 olan temel kuvvetleri çarpar, diğerlerini atlarsınız.
# 13 = 1101 -> a^8 * a^4 * a^1En Düşük Biti Denetleyin
En düşük biti denetlemek için b & 1 ifadesine bakın. Bit 1 ise devam etmeden önce geçerli tabanı biriken sonuca katın.
if b & 1: result = result * base % MODHer Turda Kaydırın ve Kare Alın
Her bitten sonra tabanın karesini alın ve üssü bir konum sağa kaydırın. Döngü, gerçekçi her girdi için yalnızca yaklaşık 30 ila 60 kez çalışır.
base = base * base % MOD
b >>= 1Hepsini Birleştirin
Sonucu 1 ile başlatın, ardından üs pozitif olduğu sürece döngüyü sürdürün. Bu hızlı üs alma fikrine ikili üs alma veya kare alarak üs alma da denir.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1Logaritmik Zamanda Çalışır
Her turda üs yarıya indiği için maliyet O(log b) olur. Böylece bir milyar çarpma işlemi yaklaşık otuz işleme iner ve her zaman sınırına rahatça sığar.
Python Size pow İşlevini Sunar
Döngüyü kendiniz yazmanız nadiren gerekir: Python'ın yerleşik pow(a, b, m) işlevi, modüler üs almayı saf C hızında sizin için gerçekleştirir.
print(pow(2, 100, MOD))Yakında Neden Önemli Olacak
Hızlı üs alma, sıradaki derste göreceğiniz Fermat yöntemli modüler ters işleminin temelidir. Şimdi ustalaşırsanız modül altında bölme kolaylaşır.
Önce Tabanı Küçültün
Döngüden önce tabanı base % MOD ile küçültün. Modülden zaten büyük olan bir taban, aksi hâlde her kare alma adımında sayıları gereksiz yere büyütür.
base = a % MODHızlı Modüler Üs Alma Ne Kadar Hızlıdır
Hızlı modüler üs alma ne kadar hızlıdır?
Özet
Artık kare alıp bitleri okuyarak sayıları O(log b) sürede devasa kuvvetlere yükseltebilirsiniz. Python'da yalnızca pow(a, b, m) çağrısını yapıp devam edin. 🚀
Sıkça Sorulan Sorular
“Hızlı Modüler Üs Alma” dersi ücretsiz mi?
Evet — “Hızlı Modüler Üs Alma” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Hızlı Modüler Üs Alma” dersinde ne öğreneceğim?
pow(a, b, m) ile üsleri hesaplayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Hızlı Modüler Üs Alma” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Bir Asal Modulo Üzerinde Çalışma
- Hızlı Modüler Üs Alma
- Fermat ile Modüler Ters
- Önceden Hesaplanmış Faktöriyellerle nCr