Javascript

Binary representation of floating-point numbers 1024 420 mezo

Binary representation of floating-point numbers

Have you ever considered the process by which computers store floating-point numbers such as 3.1416 (­ŁŁ┐) or 9.109 ├Ś 10Ôü╗┬│┬╣ (the mass of the electron in kg) in the memory which is limited by a finite number of ones and zeroes (aka bits)?

For integers (i.e., 17). It appears to be fairly straightforward. Assume we have 16 bits (2 bytes) to store the number. We can store integers between 0 and 65535 in 16 bits:

(0000000000000000) = (0)

(0000000000010001)Ôéé =
    (1 ├Ś 2Ôü┤) +
    (0 ├Ś 2┬│) +
    (0 ├Ś 2┬▓) +
    (0 ├Ś 2┬╣) +
    (1 ├Ś 2Ôü░) = (17)ÔéüÔéÇ

(1111111111111111)Ôéé =
    (1 ├Ś 2┬╣ÔüÁ) +
    (1 ├Ś 2┬╣Ôü┤) +
    (1 ├Ś 2┬╣┬│) +
    (1 ├Ś 2┬╣┬▓) +
    (1 ├Ś 2┬╣┬╣) +
    (1 ├Ś 2┬╣Ôü░) +
    (1 ├Ś 2Ôü╣) +
    (1 ├Ś 2ÔüŞ) +
    (1 ├Ś 2ÔüĚ) +
    (1 ├Ś 2ÔüÂ) +
    (1 ├Ś 2ÔüÁ) +
    (1 ├Ś 2Ôü┤) +
    (1 ├Ś 2┬│) +
    (1 ├Ś 2┬▓) +
    (1 ├Ś 2┬╣) +
    (1 ├Ś 2Ôü░) = (65535)ÔéüÔéÇ

On the off chance that we really want a marked number we might utilize two’s supplement and shift the scope of [0, 65535] towards the negative numbers. For this situation, our 16 pieces would address the numbers in a scope of [-32768, +32767].

As you would have seen, this approach will not permit you to address the numbers like – 27.15625 (numbers after the decimal point are simply being disregarded).

However, we’re not the initial ones who have seen this issue. Around Ôëł36 years ago a few brilliant people conquered this limit by presenting the IEEE 754 norm for floating-point arithmetic.

The IEEE 754 standard portrays the way (the framework) of utilizing those 16 bits (or 32, or 64 bits) to store the numbers of wider range, including the small floating numbers (smaller than 1 and closer to 0).

To get the thought behind the standard we could review the logical documentation – an approach to communicating numbers that are excessively huge or excessively little (for the most part would bring about a long string of digits) to be helpfully written in decimal structure.

As you might see from the picture, the number portrayal may be parted into three sections:

sign
division (otherwise known as significant) – the important digits (the significance, the payload) of the number
example – controls how far and in which direction to move the decimal point in the fraction
The base part we might preclude simply by settling on what it will be equivalent to. For our situation, we’ll involve 2 as a base.

Rather than utilizing every one of the 16 bits (or 32 bits, or 64 bits) to store the fraction of the number, we might share the bits and store a sign, type, and portion simultaneously. Contingent upon the numbers of bits that we will use to store the number we end up with the accompanying parts:

Floating-point formatTotal bitsSign bitsExponent bitsFraction bitsBase
Half-precision1615102
Single-precision3218232
Double-precision64111522

With this approach, the number of bits for the fraction has been reduced (i.e. for the 16-bits number it was reduced from 16 bits to 10 bits). It means that the fraction might take a narrower range of values now (losing some precision). However, since we also have an exponent part, it will actually increase the ultimate number range and also allow us to describe the numbers between 0 and 1 (if the exponent is negative).

For example, a signed 32-bit integer variable has a maximum value of 2┬│┬╣ Ôłĺ 1 = 2,147,483,647, whereas an IEEE 754 32-bit base-2 floating-point variable has a maximum value of Ôëł 3.4028235 ├Ś 10┬│ÔüŞ.

To make it possible to have a negative exponent, the IEEE 754 standard uses the biased exponent. The idea is simple – subtract the bias from the exponent value to make it negative. For example, if the exponent has 5 bits, it might take the values from the range of [0, 31] (all values are positive here). But if we subtract the value of 15 from it, the range will be [-15, 16]. The number 15 is called bias, and it is being calculated by the following formula:

exponent_bias = 2 ^ (kÔłĺ1) Ôłĺ 1

k - number of exponent bits

I’ve tried to describe the logic behind the converting of floating-point numbers from a binary format back to the decimal format on the image below. Hopefully, it will give you a better understanding of how the IEEE 754 standard works. The 16-bits number is being used here for simplicity, but the same approach works for 32-bits and 64-bits numbers as well.

Checkout the interactive version of this diagram to play around with setting bits on and off, and seeing how it would influence the final result

Here is the number ranges that different floating-point formats support:

Floating-point formatExp minExp maxRangeMin positive
Half-precisionÔłĺ14+15┬▒65,5046.10 ├Ś 10Ôü╗ÔüÁ
Single-precisionÔłĺ126+127┬▒3.4028235 ├Ś 10┬│ÔüŞ1.18 ├Ś 10Ôü╗┬│ÔüŞ

Be aware that this is by no means a complete and sufficient overview of the IEEE 754 standard. It is rather a simplified and basic overview. Several corner cases were omitted in the examples above for simplicity of presentation (i.e. -0-Ôł×+Ôł× and NaN (not a number) values)

Code examples

In the javascript-algorithms repository, I’ve added a source code of binary-to-decimal converters that were used in the interactive example above.

Below you may find an example of how to get the binary representation of the floating-point numbers in JavaScript. JavaScript is a pretty high-level language, and the example might be too verbose and not as straightforward as in lower-level languages, but still it is something you may experiment with directly in the browser:

See the Pen bitsToFloat.js by mzekiosmancik (@mzekiosmancik) on CodePen.

References

You might also want to check out the following resources to get a deeper understanding of the binary representation of floating-point numbers:

Levenshtein Distance Algorithm 1024 668 mezo

Levenshtein Distance Algorithm

Hello my fellow Padawans 

Couple days ago I had to use an algorithm for comparing string and I want to write something about Levenshtein Algorithm. This algorithm is for measure the metric distance between 2 string text. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after the Soviet mathematician Vladimir Levenshtein, who considered this distance in 1965.

Mathematically, the Levenshtein distance between two strings a, b (of length |a| and |b| respectively) is given by leva,b(|a|,|b|)

where 1(aiÔëábi) is the indicator function equal to 0 when aiÔëábi and equal to 1 otherwise, and leva, b(i,j) is the distance between the first i characters of a and the first j characters of b.

Note that the first element in the minimum corresponds to deletion (from a to b), the second to insertion and the third to match or mismatch, depending on whether the respective symbols are the same.

We can use this algorithm for string matching and spell checking

This algorithm calculates the number of edit operation that are necessary to modify one string to another string. Fro using this algorithm for dynamic programming we can use these steps :
1- A matrix is initialized measuring in the (m, n) cells the Levenshtein distance between the m-character prefix of one with the n-prefix of the other word.
2 – The matrix can be filled from the upper left to the lower right corner.
3- Each jump horizontally or vertically corresponds to an insert or a delete, respectively.
4- The cost is normally set to 1 for each of the operations.
5- The diagonal jump can cost either one, if the two characters in the row and column do not match else 0, if they match. Each cell always minimizes the cost locally.
6- This way the number in the lower right corner is the Levenshtein distance between these words.

An example that features the comparison of “HONDA” and “HYUNDAI”,

Following are two representations: Levenshtein distance between “HONDA” and “HYUNDAI” is 3.

The Levenshtein distance can also be computed between two longer strings. But the cost to compute it, which is roughly proportional to the product of the two string lengths, makes this impractical. Thus, when used to aid in fuzzy string searching in applications such as record linkage, the compared strings are usually short to help improve speed of comparisons.

Here’s the code that you can use the Levenshtein Distance and calculate percentage between 2 string.

See the Pen levenshtein.js by mzekiosmancik (@mzekiosmancik) on CodePen.

Javascript Algoritmalar─▒ – Bubble Sort 230 300 mezo

Javascript Algoritmalar─▒ – Bubble Sort

Bubble Sort okullarda ├Â─čretilen ilk algoritmad─▒r diyebiliriz. Bu algoritma verim olarak en verimsiz s─▒ralama algoritmas─▒d─▒r ancak yap─▒sal olarak anla┼č─▒lmas─▒ en kolay─▒d─▒r. Buradaki temel fikir s─▒ralanacak dizi i├žindeki elemanlar─▒n kar┼č─▒la┼čt─▒r─▒lmas─▒d─▒r. Her seferinde 2 eleman kar┼č─▒la┼čt─▒r─▒l─▒r ve sonras─▒nda yerleri de─či┼čmeden ├Ânce do─čru s─▒radalarm─▒ diye emin olur. Basit olarak :┬á
*Ilk eleman ile ikinciyi kar┼č─▒la┼čt─▒r─▒r
*E─čer ilk eleman ikinci elemandan sonra gelmeliyse yerlerini de─či┼čtirir
*Sonra ├╝├ž├╝nc├╝ eleman ile ikiyi kar┼č─▒la┼čt─▒r─▒r┬á
*E─čer┬á ikinci eleman , ├╝├ž├╝nc├╝ elemandan sonra gelecekse yerlerini de─či┼čtirir ve bu i┼člem dizinin son eleman─▒na kadar devam eder.┬á
A┼ča─č─▒daki resim anlatt─▒─č─▒m ┼ču mant─▒─č─▒ anlaman─▒za yard─▒mc─▒ olacakt─▒r.┬á

Flowchart:

├ľrnek Kod:

See the Pen Bubble Sort by mzekiosmancik (@mzekiosmancik) on CodePen.

Javascript Algoritmalar─▒ – Selection Sort 300 363 mezo

Javascript Algoritmalar─▒ – Selection Sort

Selection Sort Bubble Sort’un biraz geli┼čtirilmi┼č halidir ve elemanlar aras─▒nda d├Âng├╝ ile d├Ânerken her eleman ge├ži┼činde sadece bir se├žim yapar ve o se├žimin s─▒ralamas─▒n─▒ de─či┼čtirir.
Bu sıralama : 
*Ilk eleman─▒n en k├╝├ž├╝k oldu─čunu varsayar┬á
*Sonra bu eleman─▒ ikinci s─▒radaki de─čer ile kar┼č─▒la┼čt─▒r─▒r.
*E─čer ikinci s─▒radaki eleman ilkinden k├╝├ž├╝kse bu sefer ikinci de─čeri en k├╝├ž├╝k olarak atar.┬á
*Bu i┼člem dizinin son eleman─▒na dek devam eder.
*E─čer minimum deger ba┼člad─▒─č─▒n─▒z de─čer de─čilse yerlerini de─či┼čtirir.
A┼ča─č─▒daki resim biraz daha yard─▒mc─▒ olacakt─▒r.

Selection Sort ├çal─▒┼čmas─▒:

├ľrnek Kod:

See the Pen Selection Sort by mzekiosmancik (@mzekiosmancik) on CodePen.

Javascript Algoritmalar─▒ – Insertion Sort 300 180 mezo

Javascript Algoritmalar─▒ – Insertion Sort

Insertion Sort sonu├ž olarak bekledi─čimiz s─▒ralanm─▒┼č listeyi her eleman i├žin s─▒ralayan ├žok basit bir s─▒ralama algoritmas─▒d─▒r. Bu y├╝zden de Heap Sort yada Quick Sort kadar verimli bir s─▒ralama algoritmas─▒ de─čildir. Insertion s─▒ralamas─▒n─▒ elimizdeki bir dizi iskambil ka─č─▒tlar─▒n─▒ s─▒ralamak gibi d├╝┼č├╝nebilirsiniz. A┼ča─č─▒daki animasyonu inceledi─činizde g├Âreceksiniz elinizdeki ka─č─▒tlar─▒ s─▒ramak i├žin bir kart─▒ aradan ├žekip yerine yerle┼čtirdi─čimiz gibi ├žal─▒┼čan ve her seferinde s─▒ralanm─▒┼č bir dizi elde eden bir s─▒ralama y├Ântemi. 

Animasyon:

FlowChart:

├ľrnek Kod:

See the Pen Insertion Sort by mzekiosmancik (@mzekiosmancik) on CodePen.

Javascript Algoritmalar─▒ – Binary Search 386 878 mezo

Javascript Algoritmalar─▒ – Binary Search

Binary search s─▒ral─▒ bir dizi i├žinde arad─▒─č─▒m─▒z de─čeri bulabilmek i├žin ├žok verimli bir algoritmad─▒r.┬á Verilen s─▒ral─▒ diziyi tekrar tekrar 2 ye b├Âlerek aramaya devam eder sonunda arad─▒─č─▒ de─čerin index numaras─▒n─▒ bulana kadar. Binary search kullan─▒m─▒ i├žin bir ├Ârnek verecek olursak , diyelim ki Google Maps ile ├žal─▒┼č─▒yorsunuz ve kullan─▒c─▒dan ald─▒─č─▒n─▒z bir mekan ismini DB den gelen s─▒ral─▒ listenizden bulup o mekan─▒n koordinatlar─▒n─▒ al─▒p haritada gostermek istiyorsunuz bunun i├žin en verimli arama algoritmas─▒ Binary Search olacakt─▒r. Nedenini a├ž─▒klayacak olursak linear arama da algoritma t├╝m listeyi bastan sona gezer ve bulmaya ├žal─▒┼č─▒rd─▒ bu da binlerce mekan bilgisi i├žinden bir isim bulabilmek i├žin tek tek bastan sona hepsini incelemesi gerekti─či anlam─▒na geliyor hem uzun hemde yorucu bir i┼člem ancak binary search ile bu binlerce mekan─▒ tek tek kontrol etmek zorunda de─čiliz.

─░nsanlara bir algoritmay─▒ anlat─▒rken baz─▒ k├╝├ž├╝k detaylar─▒ s├Âylemeye gerek yoktur ├Ârne─čin bir kek yap─▒lmas─▒n─▒ istedi─čimizde buzdolab─▒n─▒ nas─▒l a├žmas─▒ gerekti─čini yada yumurtalar─▒ dolaptan ├ž─▒kar─▒p nas─▒l k─▒rmalar─▒ gerekti─čini s├Âylememize gerek kalmaz insan bu gibi k├╝├ž├╝k detaylar─▒ kendisi tamamlayarak kek yapma i┼člemini tamamlayabilirler ancak bilgisayarda bu gibi k├╝├ž├╝k detaylar┬á bilgisayar taraf─▒ndan tamamlanamaz t├╝m detaylar─▒n bilgisayara tan─▒mlanmas─▒ gerekir.

Programlama boyutunda algoritmalar─▒ uygulayabilmek i├žin algoritman─▒n t├╝m detaylar─▒n─▒ bilmek gerekiyor. Problem i├žin girdiler nedir ? ├ç─▒kt─▒s─▒ nedir ? Hangi de─či┼čkenler tan─▒mlanmal─▒ ? Bu de─či┼čkenler ne t├╝rde olmal─▒? Bir d├Âng├╝ olmal─▒ m─▒ ne gibi ko┼čullarda olmal─▒ gibi detaylar.

Hadi bu kadar bo┼č yapt─▒ktan sonra ┼ču binary search e dikkatlide g├Âz atal─▒m. Buradaki ana fikir belirtti─čimiz say─▒y─▒ bulabilmek i├žin belirli aral─▒klar─▒ takip etmek. Diyelim ki bir tahmin oyunu oynuyoruz ve bu tahmin oyununda akl─▒m─▒zdan 1 ile 100 aras─▒nda bir say─▒ tutuyoruz. Ard─▒ndan siz de bana tahminimizi s├Âyl├╝yorsunuz ve 25 diyorsunuz ve ben size Yukar─▒ diyorum. Ard─▒ndan siz 81 diyorsunuz bende size A┼ča─č─▒ diyorum. ┼×imdi biliyorsunuz ki say─▒ art─▒k k─▒rm─▒z─▒ ile i┼čaretledi─čimiz 26 ile 80 aral─▒─č─▒nda yani 25 ten k├╝├ž├╝k ve 81 den b├╝y├╝k say─▒lar─▒n hepsini elemi┼č olduk.

Her seferinde tahmininiz e─čer do─čru de─čilse kalan aral─▒ktaki say─▒lar─▒ belli tahmin edilebilir bir aral─▒─ča b├Âlerek devam ediyor. ├ť├ž├╝nc├╝ tahmininde53 diyorsunuz ve bende A┼ča─č─▒ diyorum yine ne yapm─▒┼č olduk 26-80 aral─▒─č─▒ndaki say─▒y─▒ tekrar b├Âlm├╝┼č olduk┬á

Do─čru say─▒y─▒ bulana kadar b├Âyle s├╝r├╝p giden ama sonunda say─▒y─▒ buldu─čumuz bir oyun gibi ├žal─▒┼č─▒r Binary Search.

─░┼člem s─▒ras─▒ yazacak olursak

1-Min = 1 ve Max = n

2-Max ve Min say─▒ aral─▒─č─▒nda bir integer bir de─čer tut

3-E─čer say─▒y─▒ bulduysan ├ž─▒k. Do─čru tahmin

4-E─čer tutulan say─▒dan d├╝┼č├╝k ise Min de─či┼čkenine tahmin edilen say─▒ya 1 ekleyip atama i┼člemini ger├žekle┼čtir.

5-E─čer tahmin edilen say─▒ tutulandan b├╝y├╝k ise o zaman Max de─čerini tahmin edilenden 1 ├ž─▒kar─▒p atama i┼člemini ger├žekle┼čtir.

6-2 numaral─▒ i┼čleme geri d├Ân.

See the Pen Binary Search by mzekiosmancik (@mzekiosmancik) on CodePen.

Javascript Algoritmalari – Heap Sort 709 790 mezo

Javascript Algoritmalari – Heap Sort

S─▒radaki s─▒ralama algoritmam─▒z Heap Sort yani T├╝rk├že meali ile y─▒─č─▒n s─▒ralamas─▒.

Bilgisayar bilimine g├Âre heap Sort yani y─▒─č─▒n s─▒ralamas─▒ algoritmas─▒ kar┼č─▒la┼čt─▒rma bazl─▒ bir s─▒ralama algoritmas─▒d─▒r. Heap sort geli┼čtirilmi┼č se├žimli s─▒ralama olarak da d├╝┼č├╝n├╝lebilir : yani diziyi s─▒ralanm─▒┼č ve s─▒ralanmam─▒┼č olarak b├Âl├╝mlere ay─▒r─▒r ve interaktif bir bi├žimde s─▒ralanmam─▒┼č olan b├Âl├╝m├╝ daralt─▒r son olarak bir b├╝t├╝n s─▒ralanm─▒┼č bir output ortaya ├ž─▒kar─▒r. Heap sort iyi dizayn edilmi┼č QuickSort dan daha yava┼č ├žal─▒┼čsa da , O(n log n) ├žal─▒┼čma zaman─▒nda olumlu b─▒r  avantaj─▒ vard─▒r.  Heap sort yerinde ve kullan─▒labilir bir algoritma olmas─▒na ra─čmen stabil ├žal─▒┼čan bir s─▒ralama algoritmas─▒ de─čildir. 

Heap sort ├žal─▒┼čmas─▒ s─▒ras─▒nda bir diziyi rastgele s─▒ras─▒ de─či┼čen de─čerlerle s─▒ralar.  Algoritman─▒n ilk ├žal─▒┼čma a┼čamas─▒nda elemanlar heap yap─▒s─▒na uygun olacak sekilde tekrar s─▒ralan─▒r ve heap a─čac─▒ yap─▒s─▒ a┼ča─č─▒daki animasyonda g├Âsterildi─či gibi sonucu sunar. 

Animasyon:

FlowChart:

├ľrnek Kod:

See the Pen Heap Sort by mzekiosmancik (@mzekiosmancik) on CodePen.

Javascript Algoritmalar─▒ – Merge Sort 625 598 mezo

Javascript Algoritmalar─▒ – Merge Sort

B─▒r baska s─▒ralama tekni─či ile birlikteyiz inkilizcesi Merge Sort t├╝rk├žesi birle┼čtirme kayna┼čt─▒rma s─▒ralamas─▒ olan bu algoritma 2 diziyi al─▒p k├╝├ž├╝kten b├╝y├╝─če s─▒ralamak ├╝zerine kurulmu┼čtur.

A┼ča─č─▒daki animasyondan da anlayaca─č─▒n─▒z ├╝zere 2 dizi al─▒n─▒yor daha sonra bunlar─▒ n kadar alt dizilere b├Âlerek bu alt listeleri kar┼č─▒la┼čt─▒r─▒larak results dizisine ekleme yaparak s─▒ral─▒yor.
Animasyon :

Flowchart :

├ľrnek Kod :

See the Pen Merge Sort by mzekiosmancik (@mzekiosmancik) on CodePen.

Javascript Algoritmalari – Quick Sort 453 593 mezo

Javascript Algoritmalari – Quick Sort

Merhaba arkada┼člar baz─▒ ald─▒─č─▒m notlar─▒ sizlerle paylasmak istiyorum bunlar javascript┬á ile temel algoritma sorular─▒ ve y├Ântemleri olarak nitelendirece─čimiz k├╝├ž├╝k yaz─▒lar olacak.
H─▒zl─▒ s─▒ralama
H─▒zl─▒ s─▒ralama bir dizi i├žindeki elemanlar─▒ herhangi bir ili┼čki kural─▒ koymadan d├╝md├╝z k├╝├ž├╝kten b├╝y├╝─če s─▒ralamam─▒za yarayan bir algoritma hadi bakal─▒m nas─▒l bir ┼čeymi┼č…

Bu s─▒ralama ├Ânce diziden bir ilk eleman─▒ pivot olarak belirler ve onun etraf─▒nda s─▒ralama yapmaya ba┼člar. K├╝├ž├╝kse left dizisine b├╝y├╝kse right dizisine. Yani pivot eleman her zaman ortada kal─▒cak ┼čekilde ,ondan b├╝y├╝k ve k├╝c├╝kleri s─▒ralar. Dikkat edecek olursan─▒z fonksiyonun sonunda s─▒ralanm─▒┼č olan diziyi d├Ând├╝r├╝rken left ve right dizileri i├žinde ayn─▒ metodu ca─č─▒rarak yani onlar─▒ da bir daha s─▒ralamaya koyarak geri d├Ând├╝r├╝yoruz.
S─▒ralama Animasyonu :
Sorting quicksort animation

FlowChart :

├ľrnek Kod :

See the Pen Quick Sort by mzekiosmancik (@mzekiosmancik) on CodePen.

    Join our Newsletter

    We'll send you newsletters with news, tips & tricks. No spams here.