Skip to content

Commit bb665dc

Browse files
github-actions[bot]github-actions[bot]
committed
1 parent 9378630 commit bb665dc

File tree

70 files changed

+432
-333
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

70 files changed

+432
-333
lines changed

‎1563/algebra/binary-exp.html‎

Lines changed: 23 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7977,6 +7977,18 @@
79777977

79787978

79797979

7980+
7981+
7982+
7983+
7984+
7985+
7986+
7987+
7988+
7989+
7990+
7991+
79807992

79817993

79827994

@@ -7985,6 +7997,10 @@
79857997

79867998

79877999

8000+
8001+
8002+
8003+
79888004

79898005

79908006

@@ -8267,6 +8283,10 @@
82678283

82688284

82698285

8286+
8287+
8288+
8289+
82708290

82718291

82728292

@@ -8279,7 +8299,7 @@
82798299
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
82808300

82818301
Last update:
8282-
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="July 27, 2025 06:10:49 UTC">July 27, 2025</span>&emsp;
8302+
<span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date" title="November 29, 2025 07:13:18 UTC">November 29, 2025</span>&emsp;
82838303

82848304
<!-- Tags -->
82858305

@@ -8319,7 +8339,7 @@ <h2 id="algorithm">Algorithm<a class="headerlink" href="#algorithm" title="Perma
83198339
<p>The idea of binary exponentiation is, that we split the work using the binary representation of the exponent.</p>
83208340
<p>Let's write <span class="arithmatex">$n$</span> in base 2, for example:</p>
83218341
<div class="arithmatex">$$3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1$$</div>
8322-
<p>Since the number <span class="arithmatex">$n$</span> has exactly <span class="arithmatex">$\lfloor \log_2 n \rfloor + 1$</span> digits in base 2, we only need to perform <span class="arithmatex">$O(\log n)$</span> multiplications, if we know the powers <span class="arithmatex">$a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log n \rfloor}}$</span>.</p>
8342+
<p>Since the number <span class="arithmatex">$n$</span> has exactly <span class="arithmatex">$\lfloor \log_2 n \rfloor + 1$</span> digits in base 2, we only need to perform <span class="arithmatex">$O(\log n)$</span> multiplications, if we know the powers <span class="arithmatex">$a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$</span>.</p>
83238343
<p>So we only need to know a fast way to compute those.
83248344
Luckily this is very easy, since an element in the sequence is just the square of the previous element.</p>
83258345
<div class="arithmatex">$$\begin{align}
@@ -8508,7 +8528,7 @@ <h2 id="practice-problems">Practice Problems<a class="headerlink" href="#practic
85088528

85098529
<ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
85108530
<span class="contributors-text">Contributors:</span>
8511-
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (41.95%)</li><li><a href="https://github.com/gabrielsimoes" title="gabrielsimoes" data-bi-name="contributorprofile" target="_blank">gabrielsimoes</a> (17.98%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (11.24%)</li><li><a href="https://github.com/back2sqr1" title="back2sqr1" data-bi-name="contributorprofile" target="_blank">back2sqr1</a> (5.99%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (5.62%)</li><li><a href="https://github.com/Electron1997" title="Electron1997" data-bi-name="contributorprofile" target="_blank">Electron1997</a> (3.0%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (2.62%)</li><li><a href="#" title="shark_s" data-bi-name="contributorprofile" target="_blank">shark_s</a> (2.25%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (1.87%)</li><li><a href="https://github.com/turfaa" title="turfaa" data-bi-name="contributorprofile" target="_blank">turfaa</a> (1.87%)</li><li><a href="https://github.com/roundspecs" title="roundspecs" data-bi-name="contributorprofile" target="_blank">roundspecs</a> (1.5%)</li><li><a href="https://github.com/wangwillian0" title="wangwillian0" data-bi-name="contributorprofile" target="_blank">wangwillian0</a> (0.75%)</li><li><a href="https://github.com/arjunUpatel" title="arjunUpatel" data-bi-name="contributorprofile" target="_blank">arjunUpatel</a> (0.37%)</li><li><a href="https://github.com/snymm2" title="snymm2" data-bi-name="contributorprofile" target="_blank">snymm2</a> (0.37%)</li><li><a href="https://github.com/PAndaContron" title="PAndaContron" data-bi-name="contributorprofile" target="_blank">PAndaContron</a> (0.37%)</li><li><a href="https://github.com/rskbansal" title="rskbansal" data-bi-name="contributorprofile" target="_blank">rskbansal</a> (0.37%)</li><li><a href="https://github.com/zhangdavid275" title="zhangdavid275" data-bi-name="contributorprofile" target="_blank">zhangdavid275</a> (0.37%)</li><li><a href="https://github.com/ahmedibrahim404" title="ahmedibrahim404" data-bi-name="contributorprofile" target="_blank">ahmedibrahim404</a> (0.37%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (0.37%)</li><li><a href="https://github.com/algmyr" title="algmyr" data-bi-name="contributorprofile" target="_blank">algmyr</a> (0.37%)</li><li><a href="https://github.com/vatsalsharma376" title="vatsalsharma376" data-bi-name="contributorprofile" target="_blank">vatsalsharma376</a> (0.37%)</li></ul>
8531+
<ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (41.95%)</li><li><a href="https://github.com/gabrielsimoes" title="gabrielsimoes" data-bi-name="contributorprofile" target="_blank">gabrielsimoes</a> (17.98%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (11.24%)</li><li><a href="https://github.com/back2sqr1" title="back2sqr1" data-bi-name="contributorprofile" target="_blank">back2sqr1</a> (5.99%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (5.62%)</li><li><a href="https://github.com/Electron1997" title="Electron1997" data-bi-name="contributorprofile" target="_blank">Electron1997</a> (3.0%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (2.25%)</li><li><a href="#" title="shark_s" data-bi-name="contributorprofile" target="_blank">shark_s</a> (2.25%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (1.87%)</li><li><a href="https://github.com/turfaa" title="turfaa" data-bi-name="contributorprofile" target="_blank">turfaa</a> (1.87%)</li><li><a href="https://github.com/roundspecs" title="roundspecs" data-bi-name="contributorprofile" target="_blank">roundspecs</a> (1.5%)</li><li><a href="https://github.com/wangwillian0" title="wangwillian0" data-bi-name="contributorprofile" target="_blank">wangwillian0</a> (0.75%)</li><li><a href="https://github.com/harsh-1806" title="harsh-1806" data-bi-name="contributorprofile" target="_blank">harsh-1806</a> (0.37%)</li><li><a href="https://github.com/arjunUpatel" title="arjunUpatel" data-bi-name="contributorprofile" target="_blank">arjunUpatel</a> (0.37%)</li><li><a href="https://github.com/snymm2" title="snymm2" data-bi-name="contributorprofile" target="_blank">snymm2</a> (0.37%)</li><li><a href="https://github.com/PAndaContron" title="PAndaContron" data-bi-name="contributorprofile" target="_blank">PAndaContron</a> (0.37%)</li><li><a href="https://github.com/rskbansal" title="rskbansal" data-bi-name="contributorprofile" target="_blank">rskbansal</a> (0.37%)</li><li><a href="https://github.com/zhangdavid275" title="zhangdavid275" data-bi-name="contributorprofile" target="_blank">zhangdavid275</a> (0.37%)</li><li><a href="https://github.com/ahmedibrahim404" title="ahmedibrahim404" data-bi-name="contributorprofile" target="_blank">ahmedibrahim404</a> (0.37%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (0.37%)</li><li><a href="https://github.com/algmyr" title="algmyr" data-bi-name="contributorprofile" target="_blank">algmyr</a> (0.37%)</li><li><a href="https://github.com/vatsalsharma376" title="vatsalsharma376" data-bi-name="contributorprofile" target="_blank">vatsalsharma376</a> (0.37%)</li></ul>
85128532
</ul>
85138533

85148534
</article>

‎1563/algebra/chinese-remainder-theorem.html‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7981,13 +7981,13 @@
79817981

79827982

79837983

7984-
7984+
79857985

7986-
79877986

7988-
79897987

7988+
79907989

7990+
79917991

79927992

79937993

‎1563/algebra/discrete-log.html‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7953,6 +7953,12 @@
79537953

79547954

79557955

7956+
7957+
7958+
7959+
7960+
7961+
79567962

79577963

79587964

‎1563/algebra/factorial-modulo.html‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7892,6 +7892,12 @@
78927892

78937893

78947894

7895+
7896+
7897+
7898+
7899+
7900+
78957901

78967902

78977903

‎1563/algebra/factorization.html‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -7992,13 +7992,13 @@
79927992

79937993

79947994

7995-
7995+
79967996

7997-
79987997

7999-
80007998

7999+
80018000

8001+
80028002

80038003

80048004

@@ -8008,14 +8008,14 @@
80088008

80098009

80108010

8011-
8012-
80138011

80148012

80158013

80168014

80178015

80188016

8017+
8018+
80198019

80208020

80218021

‎1563/algebra/fibonacci-numbers.html‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7964,14 +7964,14 @@
79647964

79657965

79667966

7967-
7968-
79697967

79707968

79717969

79727970

79737971

79747972

7973+
7974+
79757975

79767976

79777977

‎1563/algebra/garners-algorithm.html‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7904,6 +7904,12 @@
79047904

79057905

79067906

7907+
7908+
7909+
7910+
7911+
7912+
79077913

79087914

79097915

‎1563/algebra/linear-diophantine-equation.html‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7942,13 +7942,13 @@
79427942

79437943

79447944

7945-
7945+
79467946

7947-
79487947

7949-
79507948

7949+
79517950

7951+
79527952

79537953

79547954

‎1563/algebra/polynomial.html‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8198,13 +8198,13 @@
81988198

81998199

82008200

8201-
8201+
82028202

8203-
82048203

8205-
82068204

8205+
82078206

8207+
82088208

82098209

82108210

‎1563/algebra/sieve-of-eratosthenes.html‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7975,14 +7975,14 @@
79757975

79767976

79777977

7978-
7979-
79807978

79817979

79827980

79837981

79847982

79857983

7984+
7985+
79867986

79877987

79887988

0 commit comments

Comments
 (0)