IEEE-754 çıkarma işlemi işlevsel olarak tamdır

 (orlp.net)
3 puan yazan GN⁺ 2023-10-09 | 2 yorum | WhatsApp'ta paylaş
  • IEEE-754 kayan noktalı çıkarma işlemi, işaretli 0 ve sonuç işareti kuralları kullanılarak keyfi ikili devreler kurulmasını sağlayabilir
  • -0 false, +0 true olarak ele alındığında, varsayılan yuvarlama modunda x - y, A ∨ ¬B yani argümanları yer değiştirmiş bir IMPLY kapısı gibi çalışır
  • Bu kapı, sabit false mevcut olduğunda NOT üretilebilir ve NOT + IMPLY birleşimi işlevsel olarak tam bir mantık kapısı kümesi oluşturur
  • Python örneği, -0.0 ile 0.0 işaretlerini doğrudan ayırt ederek f_not, f_or, f_and, f_xor işlevlerinin tamamını çıkarma tabanlı olarak uygular
  • Rust örneği, f32 dizisiyle 8 bitlik tamsayıları temsil edip 23 + 19 = 42 hesabını yapar; iki 8 bitlik tamsayının toplanması için yaklaşık 120 kayan nokta komutu gerekir

IEEE-754 işaret kurallarının oluşturduğu başlangıç noktası

  • IEEE-754 kayan noktalı çıkarma işlemi işlevsel tamlığa sahiptir
  • İşlevsel olarak tam olması, yalnızca bu işlemle herhangi bir ikili devrenin kurulabileceği anlamına gelir
  • Temel nokta, IEEE 754-2019 standardının 6.3 bölümündeki işaret biti kurallarıdır
    • Çıkarma x - y, toplam x + (-y) olarak ele alınır
    • 0 bir işarete sahip olabilir; bu yüzden -0 ile +0 farklı değerler olarak değerlendirilir
    • Ancak IEEE-754 karşılaştırmalarında -0 == +0 doğrudur
    • Girdi ve sonuç NaN olmadığında, toplamın veya farkın işareti işlenenlerin işaret kurallarını izler
    • Aynı işaretli iki değerin farkı tam olarak 0 ise, roundTowardNegative dışındaki yuvarlama modlarında sonuç +0 olur
  • Sonraki kurulum, varsayılan yuvarlama modu olan roundTiesToEven varsayımıyla yapılır
    • roundTowardNegative altında da benzer şekilde çalışır

0'ların birbirinden çıkarılmasıyla oluşan doğruluk tablosu

  • Yalnızca -0 ve +0 çıkarıldığında şu sonuçlar elde edilir
    • -0 - -0 = +0
    • -0 - +0 = -0
    • +0 - -0 = +0
    • +0 - +0 = +0
  • -0 false, +0 true olarak alınırsa çıktı doğruluk tablosu şöyledir
    • 0 0 -> 1
    • 0 1 -> 0
    • 1 0 -> 1
    • 1 1 -> 1
  • Bu doğruluk tablosu A ∨ ¬B ile aynıdır ve B → A biçimindeki IMPLY kapısına karşılık gelir
    • Klasik IMPLY kapısıyla karşılaştırıldığında bu, argümanları ters çevrilmiş bir biçimdir

Sabit false varsa işlevsel olarak tam hale gelir

  • Bu doğruluk tablosu, sabit false değerine erişilebildiğinde işlevsel olarak tamdır
  • Sabit false varsa NOT kapısı üretilebilir
  • NOT + IMPLY işlevsel olarak tam bir kümedir
  • NAND ve NOR ise belirli bir sabit değer olmadan da tek başına işlevsel olarak tamdır
    • Mikroçip üretirken yalnızca tek tür bileşen üretme avantajı sağlar
    • NOT kapısı elde etmek için tutarlı bir low sinyalini yönlendirme gereği ortadan kalkar

Python ile kurulan çıkarma mantık devresi

  • Python örneği, -0.0 değerini false, 0.0 değerini true olarak tanımlar
    • IEEE-754'te +0 ile -0 karşılaştırma açısından eşit olduğundan, bunları ayırmak için işaret çıkarımı math.copysign ile yapılır
  • NOT kapısı, -0 - x işleminin 0'ın işaretini ters çevirmesi özelliğini kullanır
    • f_not = lambda x: f_false - x
    • f_not(-0.0) true olur
    • f_not(+0.0) false olur
  • OR kapısı, ikinci argümanın işaretini ters çevirdikten sonra çıkarma yapacak şekilde kurulur
    • f_or = lambda a, b: a - f_not(b)
    • Yalnızca iki argüman da -0 olduğunda false olur, diğer tüm durumlarda true verir
  • AND ve XOR da OR ile NOT birleştirilerek kurulabilir
    • f_and = lambda a, b: f_not(f_or(f_not(a), f_not(b)))
    • f_xor = lambda a, b: f_or(f_and(f_not(a), b), f_and(a, f_not(b)))

Rust ile kurulan yazılım tamsayıları

  • Rust örneği, Bit = f32 alır ve bitleri ZERO = -0.0, ONE = 0.0 ile temsil eder
  • not, or, and, xor işlevlerinin tamamını kayan noktalı çıkarma tabanlı olarak uygular ve bunlarla tam toplayıcı adder oluşturur
  • SoftU8 = [Bit; 8] ile 8 bitlik tamsayılar temsil edilir
    • to_softu8, u8 içindeki her biti ONE veya ZERO değerine dönüştürür
    • from_softu8, her elemanın işaretini kontrol ederek bunu yeniden u8 biçimine çevirir
  • Örnek program, 23 ile 19'u SoftU8 biçimine dönüştürüp topladıktan sonra 42 çıktısını verir
  • İki 8 bitlik tamsayının toplanması için yaklaşık 120 kayan nokta komutu gerekir
  • x86-64'te gerçek bir kayan nokta işaret tersleme komutu bulunmadığından, derleyici IEEE-754 kayan noktalı sayıların en üst bitini, yani işaret bitini, değiştiren bir maske ve XOR kullanır

İlgili okumalar

2 yorum

 
GN⁺ 2023-10-09
Hacker News yorumları

  • Kayan nokta komutlarının bu tür tuhaf kötüye kullanımlarının, bir DRM’in sanal makineyi karmaşıklaştırmak için kullanabileceği bir yöntem olabileceği akla geliyor.
    Sonraki adım muhtemelen bu özelliği kullanarak sıradan kaynak kodu kayan nokta tamsayıları olarak çalıştıran bir derleyici yapmak ve sıradan OS API’lerini çağırmak için FFI benzeri bir şey eklemek olurdu.

    • İlginizi çekebilecek kaynaklar: IEEE kayan nokta hatasını makine öğrenimi aktarım fonksiyonlarında kullanan http://tom7.org/grad/ ve IEEE NaN ile sonsuzluklardan mantık kapıları ve komple bir CPU yapan http://tom7.org/nand/.
    • Bu varyant Intel MMU istisna işleme ile daha önce uygulanmıştı: https://github.com/jbangert/trapcc
      Intel MMU’nun istisna işleme mekanizmasının Turing-tam olduğuna dair yapıcı bir kanıt.
      Move, Branch if Zero, Decrement komutlarını birden fazla işlemci denetim tablosu kuran C kaynak koduna dönüştüren bir assembler yaptılar; o kod çalıştıktan sonra CPU tek bir komut bile yürütmeden, istisna oluşturmaya çalışarak hesaplama yapıyor.
      İsteğe bağlı olarak assembler, değişkenleri VGA frame buffer’da gösteren ve denetimi yerel görüntüleme komutları ile weird machine trap komutları arasında geçiren X86 komutları da üretebiliyor.
    • https://github.com/xoreaxeaxeax/movfuscator ile benzer bir havası var.

  • Yalnızca IEEE-754 NaN ve sonsuzluklarla hesaplama kuran şu harika video aklıma geldi: https://www.youtube.com/watch?v=5TFDG-y-EHs

    • O kanalın tamamı, suckerpinch / Tom 7 gerçekten müthiş.
      Aşırı geek, düşünceli ve komik içerikler; sunumu da çok iyi.
      Özellikle HN okur kitlesine şiddetle tavsiye ederim.

  • Kısa öykü Coding Machines’te, benzer şekilde işaret bitinin kötüye kullanılması gerçek bir yapay zekanın dünyaya salındığına dair büyük ipucuydu.
    https://www.teamten.com/lawrence/writings/coding-machines/

  • İlgili bir kaynak olarak https://dougallj.wordpress.com/2020/05/10/bitwise-conversion... var.
    Bir IEEE-754 double değerini, argümanın bit temsilindeki alt 32 bit ve üst 32 bit tamsayı değerlerini içeren iki double’dan oluşan bir çifte dönüştüren bir uygulama; yalnızca double toplama/çıkarma/çarpma kullanıyor.

  • Doğruluk tablosuna bakınca çıkarma açıkça doğruyu koruyan bir işlem, bu yüzden gerçekte fonksiyonel olarak tam olamaz gibi görünüyor.
    Neyi kaçırıyorum?

    • Kesin konuşmak gerekirse, sabit false’a, yani -0.0’a erişiminiz varsa bileşimle fonksiyonel olarak tam.
      Bu sabit yoksa fonksiyonel olarak tam değil; herhangi bir değerden false üretebilen NAND’dan farklı.
      Yazının amacı, işaretli sıfır ve kayan nokta çıkarmadan başka bir şey kullanmadan keyfi devrelerin taklit edilebileceğini göstermekti; bunu ifade etmek için fonksiyonel tamlığın en özlü terim olduğunu düşündüm, ama yalnızca doğruluk tablosuna sıkı sıkıya bakarsak kuralları biraz esnetmiş sayılırım, bunu yazıda netleştireceğim.
    • Burada doğruyu koruyan derken tam olarak ne kastedildiğinden emin değilim, ama ipucu şu: fonksiyonel olarak tam olan tek başına çıkarma değil, çıkarma ile birlikte sabit sembol 0.
      Çıkarma ve 0 ile false’u -0.0 olarak oluşturup Wikipedia [1]’de geçen fonksiyonel olarak tam {->, _|_} kümesini elde ediyoruz.
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • Çıkarma, işaret biti açısından doğruyu koruyandır; ancak gerçek çıkarma bitleri açısından doğruyu koruyan değildir.
      Çıkarma bitinin tek başına fonksiyonel olarak tam olduğu iddiasına katılmıyorum.
      Doğruyu koruduğu için fonksiyonel olarak tam olmadığı yargısı doğru görünüyor.
    • İmlemenin doğruluk tablosu, argüman sırası ters çevrilmiş hâli altında “bu doğruluk tablosu fonksiyonel olarak tamdır [1]” diyorlar, ama bağlantı verilen Wikipedia, IMPLY tek başına fonksiyonel olarak tam değildir diye açıkça yazıyor.
      “NOT ile {AND, OR, IMPLY} içinden birini içeren her iki elemanlı bağlaç kümesi, {NOT, AND, OR, IMPLY, IFF}’in minimal fonksiyonel olarak tam altkümesidir” diyor.
      [1] https://en.wikipedia.org/wiki/Functional_completeness
    • Doğruyu korumanın fonksiyonel tamlığı neden engellediğini anlamıyorum.
      En başta doğruluk tablosunun doğruyu koruduğunu nasıl biliyoruz? Doğruluk tablosu mantıksal bir argüman değil.

  • İşlevsel tamlık herhangi bir mantık devresinin yapılabileceği anlamına geliyorsa, IEEE-754 kayan nokta çıkarma aslında Turing-tam demek mi? Yoksa değil mi?

    • Değil
      İşlevsel tamlık, Turing-tam olmak için gereken yineleme özelliğini içermez
      Turing-tamlık, işlevsel tamlıktan söz edilmeye çalışılırken sıkça yanlış kullanılır; ikisi karıştırılmış olabilir ya da bir blog yazısı/haber başlığı için daha havalı göründüğünden öyle yazılmış olabilir
      mov aslında Turing-tam değildir; jmp komutu gerekir: https://harrisonwl.github.io/assets/courses/malware/spring20...
      Homomorfik şifreleme sistemleri işlevsel olarak tamdır ama Turing-tam değildir. Çünkü yineleme, yapılan işlem sayısını sızdırarak şifrelemeyi kırar
    • Reddit'te gördüğüm ifadeyi ödünç alırsam, NAND kapısını çıkarma olarak okuyabilirsiniz
      NAND kapılarıyla Turing-tam bir makine yapabilirsiniz ama NAND kapısının Turing-tam olduğunu söylemek, bir tuğlanın içinde yaşayabileceğinizi söylemek gibidir
      Bir tuğlanın içinde yaşayamazsınız; ama tuğlalarla bir ev inşa edip içinde yaşayabilirsiniz
    • Neredeyse doğru
      “0 veya altındaysa çıkar ve dallan” tek komutlu olarak Turing-tamdır
      https://en.wikipedia.org/wiki/One-instruction_set_computer

  • Daha önce /r/programming başlığına da koymuştum, buraya da bırakıyorum
    Bir toplayıcıyı “sadece” 11 çıkarma ile uygulayabilirsiniz
    fn adder(a: Bit, b: Bit, c: Bit) -> (Bit, Bit) {
    let r0 = c - b;
    let r1 = c - r0;
    let r2 = ZERO - r0;
    let r3 = b - r1;
    let r4 = r2 - r3;
    let r5 = a - r4;
    let r6 = r4 - a;
    let r7 = ZERO - r5;
    let r8 = r7 - r1;
    let r9 = r7 - r6;
    let r10 = ZERO - r8;
    (r9, r10)
    }

  • “Yalnızca kayan nokta işlemleri kullanılarak yazılımda uygulanmış tamsayı” deniyorsa, temelde JavaScript'in number türünü int gibi kullanmaya yönelik her girişimi ile aynı şeydir

  • “İki anlamlı sayının işareti aynıysa çıktı da o işarette olmalıdır. Ama x−y'de x ile y'nin işaretleri farklıysa çıktı x'in işaretinde olmalıdır” cümlesi ya küçük bir hata içeriyor ya da işaret sözcüğünü iki farklı anlamda karıştırıyor
    x=5, y=10 gibi ikisi de pozitif işaretliyse x-y, -5 olur ve negatif işaretli çıkar
    y değişkeninin işaretinin gerçekten ters çevrildiğini varsaysak bile, -3 ve -6'yı seçersek ikincisi 6'ya çevrilir ve sonuç +3 olur; bu da x'ten farklı işaretlidir

    • x ve y'nin ikisi de pozitif işaretliyse “x−y'de x ile y'nin işaretleri farklıysa” koşulunu sağlamaz
      -3 ve -6 da aynı şekilde x ile y'nin işaretleri aynı olduğundan çıkarma için belirtilen koşulu sağlamaz
    • Sanırım “farklı” kelimesini kaçırmışsınız
      Örnekler aynı işaretle ilgili
 
asd142513 2023-10-11

Başlıkta bir hata var gibi görünüyor. Çıkarmanın tamamlandığı değil, çıkarma ile tüm işlevlerin ifade edilebildiği anlamında işlevsel olarak tam olduğu söylenmiş.