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.