Hasilkan fraktal Newton

24

Anda semua tahu metode Newton untuk memperkirakan akar suatu fungsi, bukan? Tujuan saya dalam tugas ini adalah untuk memperkenalkan Anda ke dalam aspek yang menarik dari algoritma ini.

Algoritma Newton hanya konvergen untuk kepastian, tetapi sebagian besar dari semua nilai input kompleks. Jika Anda menggambarkan konvergensi metode untuk semua nilai input di atas bidang kompleks, Anda biasanya mendapatkan fraktal yang indah seperti ini:

Fraktal Newton untuk f (x) = x ^ 3-1 Gambar dari Wikimedia commons

Spesifikasi

Tujuan dari tugas ini adalah, untuk menghasilkan fraktal tersebut. Ini berarti, bahwa Anda mendapatkan polinomial sebagai input dan harus mencetak fraktal yang sesuai sebagai gambar dalam format pilihan Anda sebagai output.

Memasukkan

Input adalah daftar bilangan kompleks yang dipisahkan spasi-putih. Mereka ditulis dengan gaya <Real part><iImaginary part>, seperti nomor ini:5.32i3.05 . Anda dapat berasumsi, bahwa jumlah input tidak lebih dari 4 tempat desimal dan lebih kecil dari 1000. Yang pertama harus tidak nol. Misalnya, ini bisa menjadi masukan untuk program Anda:

1 -2i7.5 23.0004i-3.8 i12 0 5.1233i0.1

Angka-angka ditafsirkan sebagai koefisien polinomial, dimulai dengan kekuatan tertinggi. Sepanjang spesifikasi ini, input polinomial disebut P . Input di atas sama dengan polinomial ini:

f (x) = x 5 + (-2 + 7,5 i ) x 4 + (23.0004 - 3,8 i ) x 3 + 12 i x 2 + 5,1233 + 0,1 i

Masukan mungkin datang kepada Anda baik dari stdin, dari argumen yang diteruskan ke program atau dari prompt yang ditampilkan ke program Anda. Anda dapat berasumsi, bahwa input tidak mengandung karakter spasi putih terkemuka atau tambahan.

Rendering

Anda harus membuat fraktal dengan cara berikut:

  • Pilih warna sebanyak akar P ditambah warna ekstra untuk divergensi
  • Untuk setiap angka dalam bidang yang terlihat, tentukan apakah metode tersebut konvergen dan jika ya ke root mana. Warnai titik sesuai dengan hasilnya.
  • Jangan cetak penggaris atau barang mewah lainnya
  • Cetak titik hitam pada titik-titik tersebut, yang merupakan akar polinomial untuk orientasi. Anda dapat mencetak hingga empat piksel di sekitar setiap root.
  • Temukan cara untuk memilih bidang yang terlihat dengan cara, bahwa semua akar dapat dibedakan dan tersebar luas di atasnya, jika memungkinkan. Meskipun penempatan frame output yang sempurna tidak diperlukan, saya berhak menolak untuk menerima jawaban yang memilih frame dengan cara yang tidak dapat diterima, misalnya. selalu pada koordinat yang sama, semua root berada dalam satu titik, dll.
  • Gambar output harus memiliki ukuran 1024 * 1024 piksel.
  • Waktu render maksimum 10 menit
  • Menggunakan nilai floating-point presisi tunggal sudah cukup

Keluaran

Outputnya harus berupa gambar grafik raster dalam format file pilihan Anda, dapat dibaca oleh perangkat lunak standar untuk sistem operasi merek X. Jika Anda ingin menggunakan format yang langka, pertimbangkan untuk menambahkan tautan ke situs web tempat orang dapat mengunduh pemirsa untuk itu.

Keluarkan file ke stdout. Jika bahasa Anda tidak mendukung meletakkan sesuatu untuk stdout atau jika Anda menemukan opsi ini kurang nyaman, temukan cara lain. Dengan cara apa pun, harus dimungkinkan untuk menyimpan gambar yang dihasilkan.

Batasan

  • Tidak ada perpustakaan pemrosesan gambar
  • Tidak ada perpustakaan yang menghasilkan fraktal
  • Kode terpendek menang

Ekstensi

Jika Anda menyukai tugas ini, Anda bisa mencoba mewarnai titik-titik sesuai dengan kecepatan konvergensi atau kriteria lainnya. Saya ingin melihat beberapa hasil menarik.

FUZxxl
sumber
6
Saya tidak sepenuhnya yakin apakah ini cocok sebagai kode golf. Di mata saya tugas itu terlalu rumit. Saya mungkin terbukti salah.
Joey
5
@ Joey: Memang. Saya ingin ini menjadi tantangan kode sendiri.
Joey Adams
2
... atau PPM dalam hal ini.
Joey
1
@ Joey: Niat saya adalah untuk membuat tugas yang agak sulit, karena banyak orang tidak suka tugas yang sangat mudah.
FUZxxl
1
Ini mudah dipecah menjadi tugas yang terpisah, dan jika bahasa Anda mendukung angka floating point yang kompleks secara asli maka Anda dapat menyimpan sebagian besar. Saya memiliki versi tidak sepenuhnya golf yang berjalan pada 1600 karakter, dimana 340 adalah kelas bilangan kompleks. Itu belum mengidentifikasi akar dan menggunakan warna, tapi saya mencoba melacak apa yang saya anggap bug dalam kode NR. (Menemukan akar x ^ 3-1 mulai dari -0,5 + 0,866i pasti tidak boleh menyimpang!)
Peter Taylor

Jawaban:

13

Python, 827 777 karakter

import re,random
N=1024
M=N*N
R=range
P=map(lambda x:eval(re.sub('i','+',x)+'j'if 'i'in x else x),raw_input().split())[::-1]
Q=[i*P[i]for i in R(len(P))][1:]
E=lambda p,x:sum(x**k*p[k]for k in R(len(p)))
def Z(x):
 for j in R(99):
  f=E(P,x);g=E(Q,x)
  if abs(f)<1e-9:return x,1
  if abs(x)>1e5or g==0:break
  x-=f/g
 return x,0
T=[]
a=9e9
b=-a
for i in R(999):
 x,f=Z((random.randrange(-9999,9999)+1j*random.randrange(-9999,9999))/99)
 if f:a=min(a,x.real,x.imag);b=max(b,x.real,x.imag);T+=[x]
s=b-a
a,b=a-s/2,b+s/2
s=b-a
C=[[255]*3]*M
H=lambda x,k:int(x.real*k)+87*int(x.imag*k)&255
for i in R(M):
 x,f=Z(a+i%N*s/N+(a+i/N*s/N)*1j)
 if f:C[i]=H(x,99),H(x,57),H(x,76)
for r in T:C[N*int(N*(r.imag-a)/s)+int(N*(r.real-a)/s)]=0,0,0
print'P3',N,N,255
for c in C:print'%d %d %d'%c

Menemukan batas tampilan (dan root) dengan menemukan titik konvergensi untuk sekelompok sampel acak. Kemudian menggambar grafik dengan menghitung titik konvergensi untuk setiap titik awal dan menggunakan fungsi hash untuk mendapatkan warna acak untuk setiap titik konvergensi. Lihatlah sangat dekat dan Anda dapat melihat akar ditandai.

Inilah hasil untuk contoh polinomial.

hasil misalnya polinomial

Keith Randall
sumber
Baik! Saya suka ini.
FUZxxl
14

Jawa, 1093 1058 1099 1077 karakter

public class F{double r,i,a,b;F(double R,double I){r=R;i=I;}F a(F c){return
new F(r+c.r,i+c.i);}F m(F c){return new F(r*c.r-i*c.i,r*c.i+i*c.r);}F
r(){a=r*r+i*i;return new F(-r/a,i/a);}double l(F c){a=r-c.r;b=i-c.i;return
Math.sqrt(a*a+b*b);}public static void main(String[]a){int
n=a.length,i=0,j,x,K=1024,r[]=new int[n];String o="P3\n"+K+" "+K+"\n255 ",s[];F z=new
F(0,0),P[]=new F[n],R[]=new F[n],c,d,e,p,q;for(;i<n;)P[i]=new
F((s=a[i++].split("i"))[0].isEmpty()?0:Float.parseFloat(s[0]),s.length==1?0:Float.parseFloat(s[1]));double
B=Math.pow(P[n-1].m(P[0].r()).l(z)/2,1./n),b,S;for(i=1;i<n;){b=Math.pow(P[i].m(P[i-1].r()).l(z),1./i++);B=b>B?b:B;}S=6*B/K;for(x=0;x<K*K;){e=d=c=new
F(x%K*S-3*B,x++/K*S-3*B);for(j=51;j-->1;){p=P[0];q=p.m(new
F(n-1,0));for(i=1;i<n;){if(i<n-1)q=q.m(c).a(P[i].m(new
F(n-1-i,0)));p=p.m(c).a(P[i++]);}c=c.a(d=q.r().m(p));if(d.l(z)<S/2)break;}i=j>0?0:n;for(;i<n;i++){if(R[i]==null)R[i]=c;if(R[i].l(c)<S)break;}i=java.awt.Color.HSBtoRGB(i*1f/n,j<1||e.l(c)<S&&r[i]++<1?0:1,j*.02f);for(j=0;j++<3;){o+=(i&255)+" ";i>>=8;}System.out.println(o);o="";}}}

Input adalah argumen baris perintah - mis java F 1 0 0 -1. Jalankan . Output adalah stdout dalam format PPM (ASCII pixmap).

Skala dipilih menggunakan Fujiwara terikat pada nilai absolut dari akar kompleks polinomial; Saya kemudian kalikan dengan 1,5. Saya menyesuaikan kecerahan dengan tingkat konvergensi, sehingga akar akan berada di patch paling terang. Oleh karena itu logis untuk menggunakan putih daripada hitam untuk menandai perkiraan lokasi akar (yang biayanya 41 dolar untuk sesuatu yang bahkan tidak dapat dilakukan "dengan benar". Jika saya memberi label semua titik yang konvergen ke dalam 0,5 piksel dari diri mereka sendiri kemudian beberapa root keluar tanpa label, jika saya memberi label semua titik yang menyatu dalam 0,6 piksel dari mereka sendiri maka beberapa root keluar berlabel lebih dari satu piksel, jadi untuk setiap root saya memberi label titik pertama yang ditemui untuk konvergen ke dalam 1 pixel dari dirinya sendiri ).

Gambar untuk contoh polinomial (dikonversi ke png dengan GIMP): Akar x ^ 5 + (- 2 + 7.5i) x ^ 4 + (23.0004-3.8i) x ^ 3 + 12i x ^ 2 + (5.1233 + 0.1i)

Peter Taylor
sumber
@ FuZxxl, gambar dari versi lama. Saya akan mengunggah satu dengan tingkat konvergensi nanti. Tetapi masalah dengan menandai akar adalah menentukan piksel mana yang akan ditandai. Ini adalah masalah klasik bahwa dengan floating point Anda tidak dapat menggunakan tes kesetaraan yang tepat, jadi Anda harus membandingkannya dengan epsilon. Akibatnya, saya tidak memiliki nilai "kanonik" untuk akar. Saya dapat menandai piksel yang menyatu dalam satu langkah, tetapi itu tidak menjamin untuk menandai apa pun, dan dapat menandai blok 4 piksel untuk satu root.
Peter Taylor
@ Peter Taylor: Seperti yang Anda lihat, Keith Randall juga menemukan solusi untuk masalah itu. Saya menambahkan persyaratan ini sebagai kesulitan ekstra. Salah satu pendekatan untuk melakukannya adalah menghitung piksel terdekat untuk setiap root dan kemudian memeriksa setiap piksel untuk sama dengan itu.
FUZxxl
@ FuZxxl, Anda belum mengerti maksud saya. "Pixel terdekat" dari root tidak didefinisikan dengan baik. Namun, saya bisa meretas sesuatu yang mungkin bisa digunakan untuk semua kasus uji yang Anda lakukan, dan saya mendapat kesan bahwa itu akan membuat Anda bahagia. Saya akan mewarnainya putih, bukan hitam, karena itu lebih logis.
Peter Taylor
@ Peter Taylor: Oke.
FUZxxl
6
Foto profil saya harus segera diubah menjadi x^6-9x^3+8, dirancang dengan hati-hati dengan memilih akar dan kemudian menggunakan Wolfram Alpha untuk menyederhanakan polinomial. Ok, saya curang dengan menukar rona di sekitar setelah itu di GIMP.
Peter Taylor
3

Python, 633 byte

import numpy as np
import matplotlib.pyplot as plt
from colorsys import hls_to_rgb
def f(z):
    return (z**4 - 1)
def df(z):
    return (4*z**3) 
def cz(z):
    r = np.abs(z)
    arg = np.angle(z)   
    h = (arg + np.pi)  / (3 * np.pi)
    l = 1.0 - 1.0/(1.0 + r**0.1)
    s = 0.8 
    c = np.vectorize(hls_to_rgb) (h,l,s)
    c = np.array(c)
    c = c.swapaxes(0,2) 
    return c    
x, y = np.ogrid[-1.5:1.5:2001j, -1.5:1.5:2001j]
z = x + 1j*y    
for i in range(10):
    z -= (f(z) / df(z))
zz = z
zz[np.isnan(zz)]=0
zz=cz(zz)
plt.figure()
plt.imshow(zz, interpolation='nearest')
plt.axis('off')
plt.savefig('plots/nf.svg')
plt.close()

Setelah Mempercepat dan Mempercantik (756 byte)

import numpy as np
from numba import jit
import matplotlib.pyplot as plt
from colorsys import hls_to_rgb 

@jit(nopython=True, parallel=True, nogil=True)
def f(z):
    return (z**4 - 1)   

@jit(nopython=True, parallel=True, nogil=True)
def df(z):
    return (4*z**3) 

def cz(z):
    r = np.abs(z)
    arg = np.angle(z)   

    h = (arg + np.pi)  / (3 * np.pi)
    l = 1.0 - 1.0/(1.0 + r**0.1)
    s = 0.8 

    c = np.vectorize(hls_to_rgb) (h,l,s)
    c = np.array(c)
    c = c.swapaxes(0,2) 
    return c    

x, y = np.ogrid[-1.5:1.5:2001j, -1.5:1.5:2001j]
z = x + 1j*y    

for i in range(10):
    z -= (f(z) / df(z))

zz = z
zz[np.isnan(zz)]=0
zz=cz(zz)
plt.figure()
plt.imshow(zz, interpolation='nearest')
plt.axis('off')
plt.savefig('plots/nf.svg')
plt.close()

Plot di bawah ini untuk fungsi Newton Fractal of log (z).

Newton Fractal untuk log (z)

Roti keju
sumber
Anda dapat menggunakan nama yang lebih pendek (1 karakter) dan menghapus spasi dengan menggabungkan beberapa baris menggunakan ;. Juga, hapus semua ruang yang mungkin.
mbomb007
Beberapa golf biasa mengurangi ini menjadi hanya 353 byte ! Belum mengujinya (tidak di matplotlibsini), jadi tidak ada jaminan bahwa itu masih berfungsi.
Khuldraeseth na'Barya