Karekök alma algoritması

Merhaba..Bilgisayar mühendisi olmak istiyorum,bu yüzden ders çalışma düzenimden arta kalan zamanda programlama çalışıyorum..Çalışırken hazır fonksiyonlarda,sqrt(x) diye bir ifadeye rastladım..Bu sqrt fonksiyonu x'in karekökünü buluyor..Bu fonksiyonun bilgisayara tam olarak ne yaptırdığını bulamıyorum maalesef..

Bu hazır fonksiyon olmasaydı,ben nasıl buldururdum diye düşündüm..Birkaç yol denedim,örneğin x'e kadar olan sayıların içinde karesi x olan sayıları teker teker bilgisayara denemesi komutunu vermek gibi..Ama bunun gibi yollar o kadar yavan oldu ki,büyük sayılarda bulması çok uzun sürdü..

Sorum tamamen matematiksel..Programlama ile alâkası pek yok..
Bir sayının karekökünü kısayoldan nasıl bulabiliriz ?Nasıl bir yol izlemeliyiz ?

Sanırım C çalışıyorsun. :)
sqrt fonksiyonu math.h kütüphanesinde tanımlanmış bir fonksiyondur.
sqrt komutu gayet kısa ancak, sanırım sen başka nasıl bir yoldan bulabiliriz diyorsun fakat küsüratlı sayılara ulaşmak zor olur.
Yine de düşünelim bakalım nasıl yapabiliriz.

C# de şöyle bir şey yapılabilirmiş bir dene bakalım bunu.

HTML-Kodu:

 Console.WriteLine("Bir sayı girin");

            double sayi = Convert.ToDouble(Console.ReadLine());

            long i, n = (long)sayi, t;

            double r = sayi;

            for (i = 0; i < n; i++)

            {

                r = (r + (sayi / r)) * 0.5;

                t = (long)r;

                if ((t * t) < t)

                    break;

            }

            Math.Sqrt();

            Console.WriteLine("Sayının Karekökü =" + r.ToString());

            Console.ReadLine(); 

            }

Çok teşekkür ederim cevabın için..C++ çalışıyorum C ile benzer bir dil..
Çok karışık bir algoritmaymış,inceleyeceğim bir süre..
Aslında dil olarak fark etmez,bana bunun algoritması gerekli..Algoritmalar bütün dillerde aynı olur hemen hemen..

Tükenir Kalem'den alıntı:

Çok teşekkür ederim cevabın için..C++ çalışıyorum C ile benzer bir dil..
Çok karışık bir algoritmaymış,inceleyeceğim bir süre..

C öğrenmiş miydin daha önce ?

Hayır hemen C++ ile başladım..

Tükenir Kalem'den alıntı:

Hayır hemen C++ ile başladım..

C öğrenmeden C++'a başlarsan zorlanırsın C temeldir ilk önce onu öğren, hatta ben sana öğrenebileceğin bir kaynağın linkini göndereyim.

duygu95'den alıntı:

C öğrenmeden C++'a başlarsan zorlanırsın C temeldir ilk önce onu öğren, hatta ben sana öğrenebileceğin bir kaynağın linkini göndereyim.

Hep C öğrenmeden C++ öğrenilmez diyorlar ama ben oop'a kadar ilerledim :)

Tükenir Kalem'den alıntı:

Hep C öğrenmeden C++ öğrenilmez diyorlar ama ben oop'a kadar ilerledim :)

C öğrenmeden C++ öğrenilmez demiyorum aslında sadece zorlanırsın ben de ilk bilmediğimde C++ den başlamıştım ama bir süre sonra mantığını boşverip ezberlemeye başladığımı farkettiğimde C den başlamaya karar verdim diğer türlü mantığını anlamadan direkt ezber gibi bir şey yapıyorsun gibi gelmişti bana :)

C++ dili C'den daha kolay geliyor ama bana,C daha karmaşık..Zaten üniversitede Assembly dahil tüm dilleri öğrenmeyi düşünüyorum,ilk dil olarak kendime C++'yı seçtim..Epeyce de ilerledim,bu hazır fonksiyonlar kısmı çoktan geride kaldı ama bir türlü bu soruya hızlı algoritma bulamamıştım..C# Console App açtım kodları aynen yapıştırdım,çalışıyor..
Örneğin 186513649 sayısının karekökünü 3 saniyede buldu..Ama C#'ın hazır fonksiyonu Math.Sqrt() bunu belki saniyenin binde biri sürede buluyor..Benim anlamadığım nokta bu C# dilini hazırlayanlar bu Math.Sqrt() fonksiyonuna nasıl bir yol öğretmişler ki,anında bulabiliyor..
Bu arada eklediğin kod çalışıyor ama ben hâlâ ne yaptığını anlamadım,ne yapıyor da buluyor program ? Fikrin var mı ? For döngüsü karışık..

Tükenir Kalem'den alıntı:

C++ dili C'den daha kolay geliyor ama bana,C daha karmaşık..Zaten üniversitede Assembly dahil tüm dilleri öğrenmeyi düşünüyorum,ilk dil olarak kendime C++'yı seçtim..Epeyce de ilerledim,bu hazır fonksiyonlar kısmı çoktan geride kaldı ama bir türlü bu soruya hızlı algoritma bulamamıştım..C# Console App açtım kodları aynen yapıştırdım,çalışıyor..
Örneğin 186513649 sayısının karekökünü 3 saniyede buldu..Ama C#'ın hazır fonksiyonu Math.Sqrt() bunu belki saniyenin binde biri sürede buluyor..Benim anlamadığım nokta bu C# dilini hazırlayanlar bu Math.Sqrt() fonksiyonuna nasıl bir yol öğretmişler ki,anında bulabiliyor..
Bu arada eklediğin kod çalışıyor ama ben hâlâ ne yaptığını anlamadım,ne yapıyor da buluyor program ? Fikrin var mı ? For döngüsü karışık..

Algoritmaların mantığını biliyor musun peki hiç algoritma çalıştın mı ?
For döngüsü C de detaylı bir şekilde anlatılıyor aslında yine dediğim gibi C bu işin temeli. :)

duygu95'den alıntı:

Algoritmaların mantığını biliyor musun peki hiç algoritma çalıştın mı ?
For döngüsü C de detaylı bir şekilde anlatılıyor aslında yine dediğim gibi C bu işin temeli. :)

Tabii..For,while,do while,arrays bu konuları deyim yerindeyse yalayıp yuttum..Fibonacci serisini yazdıran program,matrislerin çarpımını bulan program,mükemmel sayıları,armstrong sayılarını ...vsvs.. bulan programları hep yaptım..Yazılan for döngüsünü anlamam normâlde zor olmaz ama burada o kadar dönüşüm yapmış ki kafam karıştı..

Ekleme: long i, n = (long)sayi, t; burada ne yaptığını biliyor musun ?

Arkadaşlar ben bilgisayar müh bölümündeyim ama programlamayla hiç uğraşmadım varsa önerdiğiniz kitap-nette kaynak söyleyin inceleyeyim biraz :D Muhammed Mastar'ın C++ derslerini indirmiştim ama daha bakmadım nasıl fikriniz var mı onun videoları hakkında? Duygu C'den başla demişsin, ben de C++'tan girecektim büyük ihtimalle

MKE'den alıntı:

Arkadaşlar ben bilgisayar müh bölümündeyim ama programlamayla hiç uğraşmadım varsa önerdiğiniz kitap-nette kaynak söyleyin inceleyeyim biraz :D Muhammed Mastar'ın C++ derslerini indirmiştim ama daha bakmadım nasıl fikriniz var mı onun videoları hakkında? Duygu C'den başla demişsin, ben de C++'tan girecektim büyük ihtimalle

Kesinlikle C den başla Tükenir Kalem'e gönderdiğim linki sana da atayım ordan başla başka bir şeye gerek yok :)
Ayrıca o bahsettiğin videoları ben sevmemiştim çünkü bir sürü kuru ezber yapıyorsun mantığını bilmeden adam int x; yazıyor ama neden bilmiyorsun ben ilk videodan bıraktım bu yüzden. :)

MKE ben senin yerinde olsam programlamadan başlamazdım..Zaten senin yerinde olduğumda programlamadan başlamamış olmam da bunu kanıtlıyor :)

Önce program yazınca bilgisayarın içinde neler olur onları araştırdım ben..C'yi daha kolay öğrenirsin diyorlar ama biz zor olanı seçelim :P

Tükenir Kalem'den alıntı:

MKE ben senin yerinde olsam programlamadan başlamazdım..Zaten senin yerinde olduğumda programlamadan başlamamış olmam da bunu kanıtlıyor :)

Önce program yazınca bilgisayarın içinde neler olur onları araştırdım ben..C'yi daha kolay öğrenirsin diyorlar ama biz zor olanı seçelim :P

Önce C daha mantıklı geldi bana. Bir alıntıyı aktarayım sana:
"Ben yeni programlamaya başlayan insanlar için her zaman C öneriyorum. Çünkü her işi çabucak yapacağınız hazır fonksiyonlar yok ve tembellik yapamıyorsunuz. Bir şey istiyorsanız, genellikle onu yazmanız gerekiyor. Kaldı ki böyle olunca, ezbere bilmeniz gereken ifade (değişken tipi, fonksiyonlar vs...) çok daha az oluyor. Bu da syntax yazmayı daha çabuk öğrenmenizi sağlıyor. Syntax'i bu kadar çabuk öğrenirken, işin mantığını kullanıp, bir şeyler yapmak diğer programlama dillerine göre zor oluyor. Ve belki inanmayacaksanız ya da mantıksız gelecek ama yeni başlayan birisine verilebilecek en iyi şey bu acı tecrübeler oluyor."

Tabi bu diller hakkında en ufak bir fikrim olmadığı da bir gerçek :D

Mesele Syntax'i kullanmaksa,o zaman hiçbir dilin önemi yok..Her dilin kabûl ettiği standartlar vardır..int tamsayı demektir,bu tüm dillerde böyledir..Döngülerden olan for,her dilde fordur..Tabii C#'ta meselâ Complex Numbers sınıf bile varmış,adamlar onu bile eklemişler dile..Program yazarken her şey elinin altında,bu seni geliştirmez..Ama ben C++ öğrenirken sqrt() varmış,bunu elimle yazsam ne olur demediğim için C'yi önceden öğrenmemem bana (sanırım) bir şey kaybettirmedi..Eğer hazır fonksiyonları kullanmayıp,kendin o fonksiyonları yazmaya çalışacaksan,dilin pek de önemi yoktur..Programlama dillerinin sadece ifade farkları vardır en basitinden C'de yazı yazdırmak için print kullanırsın,C++'da cout kullanırsın,C#'ta (konsol için,şu siyah ekran) Console.Write kullanırsın..Hepsi aynı işi yapar,sadece yazımları farklı..Bunun dışında programlama dillerinin en büyük farkı,kütüphaneleridir..Şu hazır fonksiyon denen şey..Sqrt ile kök buldurma gibi,ben de tam onu soruyorum,hâlâ kodu anlamadım maalesef..

Fikri olan var mı ? Elimizde saniyeler içinde binlerce işlem yapabilen bir makine var,sırayla denetebiliriz tüm sayıları,ama nasıl eleyelim ?
Örneğin 9'un karekökünü bulurken 2'yi ve 2-3 aralığındaki reelleri boşu boşuna denemesin ?

.C yapisal programlamayi kullanir,c++ nesneye yönelik programlama.C kolay ögrenilir veya programlama kolay ögreniliri kim demişşe yalan söylemiş.Assembly ve normal makine dilini saymazsak C insandan en uzak dildir .O yüzden ögrenmesi pekte kolay olmasa gerek :).

Üniversilerde derslere bakarsaniz ilk önce C işlenir sonra C++ diğer programlama dilleri genellikle seçmeli olur veya hiç olmaz.
Tüm programlama dillerin bilmenin bir anlami yok amacinin ne oldugu önemli.Assemblye işletim sistemleri bazi kisimlari,C işletim sistemleri ve driver,C++ performans gereken programlar ve oyunlar ,Java küçük çapli programlar ve telefonlar için vb.
Hazir kütüphane fonksiyonlari özenle yazilmiştir o yüzden onlarin yaptiği sqrt fonksiyonun elle yapilandan hizli olmasi normal :).
Kabaca aklima gelen sqrt fonsiyon söyle benim.
Şimdi diyelim Float girdi diye bir değişken var ve 4 den büyük olan bir sayi girilmiş olsun.
Birde float kök=1 diye bir değişken olsun.
Ayrica float hassaslik olsun.Mesela hassaslik 0,01 olabilir,001 olabilir ne kadar küçültürsen o kadar yaklaşiriz
ve son olarakta float yaklasim olsun.
While döngüsü ile kök sayisi Girdi/2 den küçükken çalissin ve kök=kök+hassaslik iken kök sayisin karesini al ve yaklasim=girdi-kök*kök
Birde if ifadesi ekle ve döngü işlerken yaklasimin mutlak degeri ne kadar küçük oluyosa o senin seçmen gereken sayidir.Çok berbat bir algoritma ama işine yarayabilir aklima daha iyiis gelmedi suan.

cengizhanhck'den alıntı:

......
işine yarayabilir aklima daha iyiis gelmedi suan.

Yukarıdaki kodun açıklamasını yazmışsın neredeyse..Demek o hassaslığı da işin içine kattığından öyle bir yol izlemiş,ben de iki saattir bu neden böyle bir işlem yapmış diye düşünüyordum,çok teşekkür ederim..

Evet hazır fonksiyonlar gerçekten özenle yazılmış,onların hızına erişmek mümkün olmuyor pek..Burada üst matematik bilgisi konuşuyor,bunu da maalesef ben bilmiyorum henüz..

Diller hakkında,en kolay diller Visual Basic gibi diller zaten haklısın,C makineye en yakın dil..Bu arada C'yi de oop yaptılar,Objective-C adı altında,Ios yazılımında çalışan programlar için..

:) adamin yaptiği benim yazdiğimdan çok daha güzel ama naptiğini anlayamadim.Benim yazdiğim çok kaba.

Mühendislik bana göre değilmiş.Hiçbirisi ilgimi çekmiyorrr :))

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
float girdi=0;
float hassaslik=0.01;
float yaklasim=1;
float cikti=0;
cout<<"bir sayi yaziniz:";
cin>>girdi;
float kok=1;
while(kok<girdi/2)
{ kok=kok+hassaslik;
if(fabs(kok*kok-girdi)<fabs(yaklasim))
{ cikti=kok;
yaklasim=kok*kok-girdi;
}

}

cout <<"yaklasik olarak=" <<cikti;
cin>>girdi;


}
asagi yukarı anlatmak bu istediğim .ama belirteyim bu en kaba bulma yöntemi çok büyük sayilarda patlar program :).
:) ilgimi bunlar çekiyodu benim ama şartlar zaten eninde sonunda insani tipa itiyo Savaş.Seneye tercih yaparken hangisine gitsem daha az kötülük çıkar diye düşüneceksin :D.

Tercih edeceğim alanlar belli zaten. Hepsi ilgimi çekiyor benim.Ama bu tür konulara hiç ilgim yok... Nedense.

cengizhanhck'den alıntı:

.C yapisal programlamayi kullanir,c++ nesneye yönelik programlama.C kolay ögrenilir veya programlama kolay ögreniliri kim demişşe yalan söylemiş.Assembly ve normal makine dilini saymazsak C insandan en uzak dildir .O yüzden ögrenmesi pekte kolay olmasa gerek :).

Üniversilerde derslere bakarsaniz ilk önce C işlenir sonra C++ diğer programlama dilleri genellikle seçmeli olur veya hiç olmaz.
Tüm programlama dillerin bilmenin bir anlami yok amacinin ne oldugu önemli.Assemblye işletim sistemleri bazi kisimlari,C işletim sistemleri ve driver,C++ performans gereken programlar ve oyunlar ,Java küçük çapli programlar ve telefonlar için vb.
Hazir kütüphane fonksiyonlari özenle yazilmiştir o yüzden onlarin yaptiği sqrt fonksiyonun elle yapilandan hizli olmasi normal :).
Kabaca aklima gelen sqrt fonsiyon söyle benim.
Şimdi diyelim Float girdi diye bir değişken var ve 4 den büyük olan bir sayi girilmiş olsun.
Birde float kök=1 diye bir değişken olsun.
Ayrica float hassaslik olsun.Mesela hassaslik 0,01 olabilir,001 olabilir ne kadar küçültürsen o kadar yaklaşiriz
ve son olarakta float yaklasim olsun.
While döngüsü ile kök sayisi Girdi/2 den küçükken çalissin ve kök=kök+hassaslik iken kök sayisin karesini al ve yaklasim=girdi-kök*kök
Birde if ifadesi ekle ve döngü işlerken yaklasimin mutlak degeri ne kadar küçük oluyosa o senin seçmen gereken sayidir.Çok berbat bir algoritma ama işine yarayabilir aklima daha iyiis gelmedi suan.

kızma ama dediğin gibi gerçekten berbat bir algoritma
arkadaşlar işi işlem yapmak diye bilgisayara eziyet etmeyin. algoritmalarınız hızlı olmalı :)
nedir o öyle belli bir adım büyüklüğü belirleyip köke ulaşana kadar uygun adım marş.

duygu95'den alıntı:

C# de şöyle bir şey yapılabilirmiş bir dene bakalım bunu.

HTML-Kodu:

 Console.WriteLine("Bir sayı girin");

            double sayi = Convert.ToDouble(Console.ReadLine());

            long i, n = (long)sayi, t;

            double r = sayi;

            for (i = 0; i < n; i++)

            {

                r = (r + (sayi / r)) * 0.5;

                t = (long)r;

                if ((t * t) < t)

                    break;

            }

            Math.Sqrt();

            Console.WriteLine("Sayının Karekökü =" + r.ToString());

            Console.ReadLine(); 

            }

burada matematik devreye giriyor. sizleri bu bölümlere alırken matematik bilmenizi/öğrenmenizi bunun için istiyorlar. yukarıdaki algoritmada yapılansa her adımda eldeki mevcut bir kök değerine (kökü alınacak sayı)/(eldeki kök değeri) kadar bir sayı eklenip 2'ye bölünmesi ve yeni bir eldeki kök değeri elde edilmesi. kısaca kodu yazan Newton metoduyla köke yaklaşmayı düşünmüş, muhtemelen 5-6 adımla istediğiniz hassasiyette bir kök bulacaktır. daha iyi algoritmalar vardır muhakkak ama bu işinizi görüyor olmalı. ayrıca da sqrt() gibi fonksiyonların bunlardan çok daha iyi algoritmalarla çalıştığından emin olabilirsiniz :) .

gereksizyorumcu'den alıntı:

burada matematik devreye giriyor. sizleri bu bölümlere alırken matematik bilmenizi/öğrenmenizi bunun için istiyorlar. yukarıdaki algoritmada yapılansa her adımda eldeki mevcut bir kök değerine (kökü alınacak sayı)/(eldeki kök değeri) kadar bir sayı eklenip 2'ye bölünmesi ve yeni bir eldeki kök değeri elde edilmesi. kısaca kodu yazan Newton metoduyla köke yaklaşmayı düşünmüş, muhtemelen 5-6 adımla istediğiniz hassasiyette bir kök bulacaktır. daha iyi algoritmalar vardır muhakkak ama bu işinizi görüyor olmalı. ayrıca da sqrt() gibi fonksiyonların bunlardan çok daha iyi algoritmalarla çalıştığından emin olabilirsiniz :) .

Öğretmenim Newton metodunu araştırdım sayenizde..Çok çok teşekkür ederim..Şimdi kodları gerçekten anladım,aslında Cengiz arkadaşımız sayesinde adamın bu kodlarla sürekli daha yakın bir değeri buldurmaya çalıştığını anlamıştım..Ama bu yolu nereden akıl ettiğini anlamamıştım,Newton metodundaki teğet açıklamasıyla bunu da anladım sayenizde.Bu arada aynı programı C++ ile yaptım,arada framework perdesi olmadığından gözle görülür bir şekilde sqrt() fonksiyonu ile aynı hızda buldu..(Yâni saniye olarak fark yok,ama salise ölçümünde fark olabilir)

Bu algoritma hızlı..Newton metodundan daha hızlı bir yol olabilir mi öğretmenim ?
İlginiz için teşekkür ederim..

belki denediğiniz sayılarda sqrt() ile yakın sonuçlar vermiş olabilir ama Newton dan çok daha hızlı hesaplama yöntemleri eminim ki mevcuttur. şu an için kök bulmada daha efektif hangi metod var bilmiyorum, Newton-Raphson çok genel bir yöntem yani tüm fonksiyonlarda kullanılabildiği için direkt karekök bulma gibi çok dar bir kullanımda geri kalacağı kesin. C# veya C++ hangi algoritmaları kullanıyor onları da bilmiyorum açıkcası kodlardan anlamıyorum ama demek istediğim kök bulmak çok temel bir işlem bu yüzden kullandığınız dilin hazır fonksiyonu bırakın algoritma olarak değişken seçimlerinde bile optimize edilmiştir.

burada esas mesele böyle temel işlemlerin yapılmasını sağlayan güzel algoritmaların olduğunu bilmekle beraber mümkünse hazır olanı kullanmaktır. bizim gelişim yapmaya çalışacağımız hazır olmayanı yazarken olmalı. hazır olanı geliştirmek programlama dilini yazanların problemi :)

Haklısınız tabii,onların hazır fonksiyonu ile yarışmam mümkün değil..Hem uzman matematikçiler ve mühendisler çalışıyor,hem de bilgileri çok çok daha ileri seviyede..Benim amacım da dediğiniz gibi,hazır olmayanı yazmayı öğrenmek..Bunun için önüme gelen bütün problemleri çözmeye çalışıyorum ki,var olan bilgilerimle neler yapabilirim diye ufkum açılsın..Tekrar teşekkür ederim ilginiz için :o

En meşhur algoritmalar Methods of computing square roots - Wikipedia, the free encyclopedia burda. Anlayabilirsen :(

Admin'den alıntı:

En meşhur algoritmalar Methods of computing square roots - Wikipedia, the free encyclopedia burda. Anlayabilirsen :(

Türkçe'sini bile birkaç dk inceleyince anlıyorum..Sık kullanılanlara ekledim öğretmenim,İngilizce şart..Sözlük ile anlamaya çalışırım bol bir vakit bulduğumda..

Teşekkür ederim..