Evolution of an Algorithm

In linear algebra, the Coppersmith–Winograd algorithm, named after Don Coppersmith and Shmuel Winograd, was the asymptotically fastest known matrix multiplication algorithm until 2010. It can multiply two ${\displaystyle n\times n}$ matrices in ${\displaystyle O(n^{2.375477})}$ time. This is an improvement over the naïve ${\displaystyle O(n^{3})}$ time algorithm and the ${\displaystyle O(n^{2.807355})}$ time Strassen algorithm. Algorithms with better asymptotic running time than the Strassen algorithm are rarely used in practice, because the large constant factors in their running times make them impractical. It is possible to improve the exponent further; however, the exponent must be at least 2 (because an ${\displaystyle n\times n}$ matrix has ${\displaystyle n^{2}}$ values, and all of them have to be read at least once to calculate the exact result).

In 2010, Andrew Stothers gave an improvement to the algorithm, ${\displaystyle O(n^{2.374}).}$ In 2011, Virginia Williams combined a mathematical short-cut from Stothers' paper with her own insights and automated optimization on computers, improving the bound to ${\displaystyle O(n^{2.3728642}).}$ In 2014, François Le Gall simplified the methods of Williams and obtained an improved bound of ${\displaystyle O(n^{2.3728639}).}$

The Coppersmith–Winograd algorithm is frequently used as a building block in other algorithms to prove theoretical time bounds. However, unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware.

Source: Wikipedia, Coppersmith–Winograd algorithm

Karatsuba Fast Multiplication Algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most  single-digit multiplications in general (and exactly  when n is a power of 2). It is therefore faster than the classical algorithm, which requires n² single-digit products. For example, the Karatsuba algorithm requires 3¹⁰ = 59,049 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 2¹⁰), whereas the classical algorithm requires (2¹⁰)² = 1,048,576.

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm is even faster, for sufficiently large n. Source: https://en.wikipedia.org/wiki/Karatsuba_algorithm

Pseudocode:

procedure karatsuba(num1, num2)
  if (num1 < 10) or (num2 < 10)
    return num1*num2

  // calculates the size of the numbers
  M = max(size_base10(num1), size_base10(num2))
  N = M/2

  // split the digit sequences about the middle
  high1, low1 = split_at(num1, N)
  high2, low2 = split_at(num2, N)

  // 3 calls made to numbers approximately half the size
  z0 = karatsuba(low1,low2)
  z1 = karatsuba((low1+high1),(low2+high2))
  z2 = karatsuba(high1,high2)

  return (z2*10^(2*N))+((z1-z2-z0)*10^(N))+(z0)

Implementation:

public static BigInteger karatsuba(BigInteger x, BigInteger y) {

  // cutoff to brute force
  int M = Math.max(x.bitLength(), y.bitLength());
  if (M <= 2000) return x.multiply(y); // optimize this parameter
  
  // number of bits divided by 2, rounded up
  int N = (M / 2) + (M % 2);
  
  // x = a + 2^N b, y = c + 2^N d
  // x = low1 + 2^N high1, y = low2 + 2^N high2
  BigInteger high1 = x.shiftRight(N);
  BigInteger low1 = x.subtract(high1.shiftLeft(N));
  BigInteger high2 = y.shiftRight(N);
  BigInteger low2 = y.subtract(high2.shiftLeft(N));
  
  // compute sub-expressions
  BigInteger z0 = karatsuba(low1, low2);
  BigInteger z1 = karatsuba(low1.add(high1), low2.add(high2));
  BigInteger z2 = karatsuba(high1, high2);
  
  return z0.add(z1.subtract(z0).subtract(z2).shiftLeft(N)).add(z2.shiftLeft(2*N));
}

Source: http://introcs.cs.princeton.edu/java/99crypto/Karatsuba.java.html

Товьёгтой, нийлмэл PDF файл үүсгэх нь

Хичээлийн улирлын эцэст, шалгалтын өмнөхөн, оюутнууд бид баахан PPT, PDF файл сөхөж харах хэрэгтэй болдог. Жишээлэхэд одоо авч буй Network & Internet Security хичээл гэхэд л 37 PPT, PDF файл хосолсон слайд, нэмэлт унших материалтай. Энэ бүх файлыг нэгбүрчлэн нээнэ гэдэг их төвөгтэйн дээр, нэгдсэн хайлт хийх боломжоор тун маруу.

PPT файлыг PDF формат руу хөрвүүлээд, гарсан PDF файлуудаа Линуксын pdfunite коммандаар хялбархан нэгтгэж болох ч, товьёг гаргаж өгдөггүй болохоор баахан чамлалттай. Нэг том PDF файл дотроо хүссэн хичээл рүү гээ үсэрч чадаж байвал нь дөхөмтэйсэн.

Ямартай ч, хичээлийнхээ слайдыг бүгдийг нь PDF рүү хөрвүүлчихлээ. pdfdir гэх нээлттэй эхийн програм ашиглаад товьёгтой, нэг том PDF файл үүсгэх гэтэл алдаа заагаад болсонгүй. Алдааг нухаж байх зав байсангүй тул, дараагийн програм болох Sejda Console-г туршиж үзэв. 

sejda-console merge -b one_entry_each_doc -f $(ls netsec/*.pdf) -o NetSec-All-Slides.pdf

Ер нь яг санасанаар нэгтгэж байна. Гарсан үр дүн нь энэ:

Хичээлийн хуваарь болон шалгалтын асуултын тоймыг хамгийн эхэнд тавьж өгөөд, өнөө 37 слайдаа бүгдийг нь нэгтгээд авлаа. Нийт 2,536 хуудастай томоо PDF файл үүсч. Одоо ингээд хичээлийн бүх слайдаас нэг дор хайлт хийх, хүссэн хичээлийн, хүссэн сэдэв рүү хулганы нэг товшилтоор очих боломжтой болов. 4 хоногийн дараах шалгалтаас өмнө лав бүх слайдаа хэд гурав гүйлгээд харчих нь ээ. Болоо ш дэ :)

Өөр бас нэг анзаарсан зүйл нь хэрэв тусдаа байгаа PDF файлуудаа эвтэйхэн паттернтай нэрлэчихвэл нь паттерн тус бүрээр PDF файл үүсгэж болох нь. Жишээ нь энэ хичээлийн слайдууд дараах үндсэн гурван төрлийн слайдуудаас бүрдэж байгаа: 1) Corporate Computer Security ном; 2) CERT-ийн слайд; 3) Cisco-н слайд.

Corporate Computer Security номын слайдын нэр '-bk' тэмдэгт агуулж байгаа тул доорх коммандаар зөвхөн энэ номын слайдуудыг нэгтгэж болох нь:

sejda-console merge -b one_entry_each_doc -f $(ls netsec/*-bk*.pdf) -o CorpCompSecBook.pdf

CERT-н слайдын нэр '-cert' тэмдэгт агуулж байгаа тул доорх коммандаар зөвхөн CERT-н слайдыг нэгтгэж болох нь:

sejda-console merge -b one_entry_each_doc -f $(ls netsec/*-cert*.pdf) -o CERT-Slides.pdf

Cisco-н слайдууд 'Cisco' тэмдэгт агуулж байгаа тул доорх коммандаар зөвхөн Cisco-н слайдуудыг нэгтгэж болох нь:

sejda-console merge -b one_entry_each_doc -f $(ls netsec/*Cisco*.pdf) -o Cisco-Slides.pdf

Эцэст нь, ингэхэд энэ нөхөр ямар файлуудыг нэгтгэчихэв гэж та гайхаж байж магад. Хариу нь энэ:

[bsanchin@bsanchin-linux netsec]$ ls -1 | while read f; do du -h $f; done | awk '{print $2, $1}' | column -t

W00-1-Syllabus.pdf                                                   384K

W00-2-Final_Exam_Study_Topics.pdf                                    288K

W01-bk1-The_Threat_Environment.pdf                                   7.2M

W01-bk2-Planning_and_Policy.pdf                                      9.5M

W01-cert-Governance.pdf                                              1.1M

W01-cert-Risk_Management.pdf                                         1.2M

W02-Ch01-Cisco-Introduction_to_Switched_Networks.pdf                 464K

W02-Ch02-Cisco-Introduction_to_Switched_Networks.pdf                 1.3M

W02-Ch03-Cisco-WLANs.pdf                                             896K

W02-Ch04-Routing_Concepts.pdf                                        1.7M

W03-cert-Demystifying_IPv6.pdf                                       3.2M

W03-IP_Fundamentals-CCNA1v3.1_Mod09.pdf                              1016K

W03-The_OSI_Model_and_Security.pdf                                   896K

W04-bk-Security_Networks.pdf                                         9.3M

W04-cert-LAN_security_using_switch_featuresv2.pdf                    1.8M

W04-Suppl1-Securing_the_LAN.pdf                                      5.2M

W04-Target_Breach.pdf                                                5.2M

W05-cert-Network_Security-Wireless.pdf                               1.1M

W05-Merging_LANs,_WLANS,_and_controller-based_Wireless_Networks.pdf  2.8M

W06-bk-Access_Control.pdf                                            12M

W06-cert-Network_Access_Security.pdf                                 1.7M

W06-Password_Recovery_Procedure_for_the_2600_Router.pdf              20K

W07-bk-Firewalls.pdf                                                 12M

W07-cert-Network_Security_Enterprise_Tools.pdf                       2.1M

W08-bk-Host_Hardening.pdf                                            9.1M

W08-cert-Network_Security_Host_Hardening.pdf                         688K

W09-bk-Data_Protection.pdf                                           8.0M

W09-cert-Mobile_Device_Security.pdf                                  4.4M

W09-cert-Threats_to_Mobile_Device.pdf                                2.4M

W09-Implementing_VPN_-_Cisco-CCNA.pdf                                4.5M

W10-cert-Insider_Threat.pdf                                          3.2M

W11-bk-Application_Security.pdf                                      6.0M

W11-Common_Developer_Crypto_Mistakes.pdf                             372K

W12-bk-Data_Protection.pdf                                           7.4M

W13-bk-Incident_and_Disaster_Response.pdf                            8.6M

W13-cert-IncidentHandlingResponse.pdf                                1.9M

W14-cert-Cloud_Computing_Security.pdf                                2.2M

W15-MS-cert1-Mobile_Threats.pdf                                      2.4M

W15-MS-cert2-Mobile_Device_Security.pdf                              4.4M

[bsanchin@bsanchin-linux netsec]$ 

Яг энэ постыг уншаад сууж байгаа эрхэм та оюутан бол шалгалтад тань өндөр амжилтыг хүсье!