05/17/17

Exploring Fibonacci Fractions with Julia

Recently, I came across a fascinating blog and video from Mind your Decisions. It is about how a fraction
\frac{1}{999,999,999,999,999,999,999,998,,999,999,999,999,999,999,999,999}
would show the Fibonacci numbers in order when looking at its decimal output.

On a spreadsheet and most standard programming languages, such output can not be attained due to the limited precision for floating point numbers. If you try this on R or Python, you will get an output of 1e-48.
Wolfram alpha,however,allows arbitrary precision.

In Julia by default we get a little better that R and Python

julia> 1/999999999999999999999998999999999999999999999999
1.000000000000000000000001000000000000000000000002000000000000000000000003000002e-48
 
julia> typeof(ans)
BigFloat

We observe here that we are getting the first few Fibonacci numbers 1, 1, 2, 3. We need more precision to get more numbers. Julia has arbitrary precision arithmetic baked into the language. We can crank up the precision of the BigFloat type on demand. Of course, the higher the precision, the slower the computation and the greater the memory we use. We do that by setprecision.

julia> setprecision(BigFloat,10000)
10000

Reevaluating, we get

julia> 1/999999999999999999999998999999999999999999999999
1.00000000000000000000000100000000000000000000000200000000000000000000000300000000000000000000000500000000000000000000000800000000000000000000001300000000000000000000002100000000000000000000003400000000000000000000005500000000000000000000008900000000000000000000014400000000000000000000023300000000000000000000037700000000000000000000061000000000000000000000098700000000000000000000159700000000000000000000258400000000000000000000418100000000000000000000676500000000000000000001094600000000000000000001771100000000000000000002865700000000000000000004636800000000000000000007502500000000000000000012139300000000000000000019641800000000000000000031781100000000000000000051422900000000000000000083204000000000000000000134626900000000000000000217830900000000000000000352457800000000000000000570288700000000000000000922746500000000000000001493035200000000000000002415781700000000000000003908816900000000000000006324598600000000000000010233415500000000000000016558014100000000000000026791429600000000000000043349443700000000000000070140873300000000000000113490317000000000000000183631190300000000000000297121507300000000000000480752697600000000000000777874204900000000000001258626902500000000000002036501107400000000000003295128009900000000000005331629117300000000000008626757127200000000000013958386244500000000000022585143371700000000000036543529616200000000000059128672987900000000000095672202604100000000000154800875592000000000000250473078196100000000000405273953788100000000000655747031984200000000001061020985772300000000001716768017756500000000002777789003528800000000004494557021285300000000007272346024814100000000011766903046099400000000019039249070913500000000030806152117012900000000049845401187926400000000080651553304939300000000130496954492865700000000211148507797805000000000341645462290670700000000552793970088475700000000894439432379146400000001447233402467622100000002341672834846768500000003788906237314390600000006130579072161159100000009919485309475549700000016050064381636708800000025969549691112258500000042019614072748967300000067989163763861225800000110008777836610193100000177997941600471418900000288006719437081612000000466004661037553030900000754011380474634642900001220016041512187673800001974027421986822316700003194043463499009990500005168070885485832307200008362114348984842297700013530185234470674604900021892299583455516902600035422484817926191507500057314784401381708410100092737269219307899917600150052053620689608327700242789322839997508245300392841376460687116573000635630699300684624818301028472075761371741391301664102775062056366209602692574850823428107600904356677625885484473810507049252476708912581411411405930102594397055221918455182579303309636633329861112681897706691855248316295261201016328488578177407943098723020343826493703204299739348832404671111147398462369176231164814351698201718008635835925499096664087184867000739850794865805193502836665349891529892378369837405200686395697571872674070550577925589950242511475751264321287522115185546301842246877472357697022053e-48

That is looking much better. However it we be nice if we could extract the Fibonacci numbers that are buried in that long decimal. Using the approach in the original blog. We define a function

y(x)=one(x)-x-x^2

and calculate the decimal

a=1/y(big"1e-24")

Here we use the non-standard string literal big"..." to insure proper interpretation of our input. Using BigFloat(1e-24)) would first construct at floating point with limited precision and then do the conversion. The initial loss of precision will not be recovered in the conversion, and hence the use of big. Now we extract our Fibonacci numbers by this function

function extract_fib(a)
   x=string(a)
   l=2
   fi=BigInt[]
   push!(fi,1)
   for i=1:div(length(x)-24,24)
        j=parse(BigInt,x[l+1+(i-1)*24:l+i*24])
        push!(fi,j)
   end
   fi
end

Here we first convert our very long decimal number of a string and they we exploit the fact the Fibonacci numbers occur in blocks that 24 digits in length. We get out output in an array of BigInt. We want to compare the output with exact Fibonacci numbers, we just do a quick and non-recursive implementation.

function fib(n)
    f=Vector{typeof(n)}(n+1)
    f[1]=f[2]=1;
    for i=3:n+1
       f[i]=f[i-1]+f[i-2]
    end
    f
end

Now we compare…

fib_exact=fib(200);
fib_frac=extract_fib(a);
for i in eachindex(fib_frac)
     println(fib_exact[i], " ", fib_exact[i]-fib_frac[i])
end

We get a long sequence, we just focused here on when the discrepancy happens.

...
184551825793033096366333 0
298611126818977066918552 0
483162952612010163284885 0
781774079430987230203437 -1
1264937032042997393488322 999999999999999999999998
2046711111473984623691759 1999999999999999999999997
...

The output shows that just before the extracted Fibonacci number exceeds 24 digits, a discrepancy occurs. I am not quite sure why, but this was a fun exploration. Julia allows me to do mathematical explorations that would take one or even two orders of magnitude of effort to do in any other language.

09/29/16

Making your own persistent USB bootable Ubuntu Distro: the easy way

I had a recent Ubuntu install with customizations that I wanted to be able to put it on a USB, boot into it on another machine and be able to modify its contents by, installing new packages, editing files, etc…

PinguyBuilder to the rescue

So after a number of false starts. I stumbled upon PinguyBuilder. I followed the excellent instructions at maketecheasier, with the slight modification of checking the PinguyBuilder site for the the latest version. I used the backup option to get all the tweaks on home directory, and my none deb packages in. My Ubuntu was a derivative the standard Xubuntu 16.04 distro.

Moving the ISO to the USB

The generated iso file could then be installed usb-creator-gtk, or if are working on windows, Rufus. At this point I could nicely boot using my USB stick. I could not, however, write anything persistently on the USB. If I create some file, and then reboot, it would be gone!

Making the USB persistent

First I need to create casper-rw file that would be identified by boot-loader as space to write on. I was happy with 2GB, so this what I did by adopting the instructions on StackExchange post:

I created an empty 2GB file

dd if=/dev/zero of=casper-rw bs=1M count=2048

You can changed count to whatever size of persistent storage you want. I then had to format that space into something that Linux would be able to read

mkfs.ext4 -F casper-rw

The next step was to change /boot/grub/grub.cfg file on the USB to have the following menu-entry at the beginning.

menuentry "Xubuntu in persistent mode" {
    set gfxpayload=keep
    linux   /casper/vmlinuz  file=/cdrom/preseed/custom.seed boot=casper persistent iso-scan/filename=${iso_path} quiet splash --
    initrd  /casper/initrd.gz
}

Finally, I modified /isolinux/isolinux.cfg to include the extra label

label persistent 
  menu label live - boot the Live System
  kernel /casper/vmlinuz
  append  file=/cdrom/preseed/custom.seed boot=casper persistent initrd=/casper/initrd.gz quiet splash --

et voilà!

07/11/15

On terrorism and the hate that follows

I worry less about the damage to live and property from acts of terror, than the waves of hate that soon follow. The damage due to hate is always much worse. Hate brings out the worst in humans. It locks the mind in inescapable focus on violence. All noble ideas, and worthy aspirations fall by the wayside as survival becomes the primary preoccupation. When that happens, I sense that the terrorists have already won.

07/11/15

الكراهية أخطر من الإرهاب

أرى نفسي أقل قلقاً من الموت و الدمار الناتج من الأعمال الإرهابية بالمقارنة لموجات الكراهية التي تتبعها. الضرر و الخسارة الناتجة من الكراهية التي تولدها هذه الأعمال أشد خطورة.
الكراهية تسقم القلوب و تبرز أقبح ما في البشر.
الكراهية تسجن العقل في دائرة لا نهائية في التركيز علي العنف.
كل الأفكار النبيلة و الطموحات الشريفة تسقط عندما يكون الهم الشاغل هو البقاء.
عندما يحدث ذالك أشعر أن الإرهاب قد نال غايته.

07/11/15

Herodotus on Decision Making

A decision was wise, even though it led to disastrous consequences, if the evidence at hand indicated it was the best one to make; and a decision was foolish, even though it led to the happiest possible consequences, if it was unreasonable to expect those consequences.

03/7/14

Nepomuk Pains

Recently I ran into a nasty situation on Kubuntu desktop where a host of crucial KDE components would cease to work. Chiefly amongst them were:

  1. No instances of Dolphin would start
  2. The kickoff launcher would not work 
  3. The KDE activity manager was crashing. 

I suspected the Nepomuk might be the culprit and I was right.  I stopped it by running

qdbus org.kde.NepomukServer /nepomukserver quit

I then wiped out its data by running

rm -r .kde/share/apps/nepomuk/

Finally I got it started again by runing

nepomukserver

…and my problems were solved.

Trying to search for a solution to this problem, I found people suggesting that one would wipe the ~/.kde folder and start afresh. That sounded too drastic and a great deal of my customizations would have been lost in the process.

01/6/14

The gods they make

The gods they make capture their fears, their ignorance, and their desire to control.
Their gods share their grotesque outlook, yet they fully capture their aspirations.
Aspirations of dominance, control, and subjugation of others.
Aspirations of meek and mean-spirited human “beings”.
The wretches are blind to human potential!

10/2/12

Using Python and wget to download certain file types from a web-page

Recently I wanted to download all the movies in Mackay’s information theory course. That was a great deal of files and I though it would too tedious to try to do it using the browser or even manual wget. So digging around, I found this decent tutorial on python HTML processing. I also dug around some information on parsing URLs. I combined that with my knowledge of python’s subprocess and put together this nice piece of code.

 

#!/usr/bin/python

import sgmllib

class MyParser(sgmllib.SGMLParser):
"A simple parser class."

def parse(self, s):
"Parse the given string 's'."
self.feed(s)
self.close()

def __init__(self, verbose=0):
"Initialise an object, passing 'verbose' to the superclass."

sgmllib.SGMLParser.__init__(self, verbose)
self.hyperlinks = []

def start_a(self, attributes):
"Process a hyperlink and its 'attributes'."

for name, value in attributes:
if name == "href":
self.hyperlinks.append(value)

def get_hyperlinks(self):
"Return the list of hyperlinks."

return self.hyperlinks

import urllib, sgmllib

# Get something to work with.
webPage="http://www.inference.phy.cam.ac.uk/itprnn_lectures/"
f = urllib.urlopen(webPage)
s = f.read()

# Try and process the page.
# The class should have been defined first, remember.
myparser = MyParser()
myparser.parse(s)

# Get the hyperlinks.
links=myparser.get_hyperlinks()
print links

movies=[x for x in links if x.endswith('mp4')]
print movies

import urlparse
movieURLs=[urlparse.urljoin(webPage,x) for x in movies]
print movieURLs

from subprocess import call

for movieURL in movieURLs:
call(["wget -c "+movieURL],shell=True)
06/12/12

موقعة الجمل و البحث عن الثورة

في يوم 2 فبراير 2011 كنت واقف في صف الدفاع الثاني عند الشارع  الفارق بين جامع عمر مكرم و مبني المجمع في ميدان التحرير. كان دوي المعركة أمامنا مرعب و كنا نتضرع الله ليثب الله أقدامنا و يقوي عزائمنا و يذود عنا شر من يريدون لروح بعثت من جديد أن توأد و لفجر الحرية أن ينزوي. وقفت مع الثوار من الإخوان و غيرهم و نظرنا صوب السماء و هتفنا بصدق لم أشعر به من قبل “يا رب!”. كان للإخوان المسلميين دور مهم في هذا اليوم. كانوا يعملون بإخلاص و تفاني لتنظيم الصفوف و رأب أي صدع أو خلل في الدفاع.
 مشهدان دائما استحضرهم كلما أصابني حنق من تصرفات الإخوان المسلمين. المشهد الأول  لشاب أحسبه من الإخوان مشجوج الرأس و مكسور الذراع. كان الشاب يحمل في يده اليسري حجراً و يحجل بعزيمة يقشعر لها البدن للصفوف الأمامية للدفاع عند الميدان. المشهد الثاني لسيدة في منتصف العمر و هي تدخل الميدان في وسط المعمعة. قالت لنا هذه السيدة: أنا من الإخوان المسلمين، أنا زوجة و أم، أنا معكم في هذه المعركة و أسأل من الله الشهادة. قالت هذه الكلمات البسيطة بصدق نفذ إلي القلوب و جعلتني أبكي أنا و من معي. 
كنا معاً صفاً واحداً و للحظات ذابت الأشكال و الصور و انقشعت الأيدلوجيات و تجلت حقيقة ربانية  يصعب وصفها و ابتذالها في كلمات.
 كنت في ذهابي للميدان دائما أبحث في الوجوه و العيون عن من رأي هذه الحقيقة. كنت أبحث عن الثورة… و مازلت ابحث.

اليوم نجد حرباً جديدة من أعداء هذه الروح الوليدة. يريدون أن يشوهوا لحظة تاريخه  في أستحضارها أمل لوحدتنا. يدعون كذباً أن الإخوان المسلميين هم من قتل و ذبح في هذا اليوم و ينكرون عليهم دفاعهم و استبسالهم. إن وجدوا في الشعب أذن صاغية  لمثل هذه الأقاويل سنفقد مضمون الثورة و لن يكون هناك أي أمل لاقتفاء أثر هذه اللحظات الصادقة.
 
للأسف مهد الطريق لهذه الحرب قيادات الأخوان بعد أن باعدوا بين شبابهم و الثوار، بعد أن سعوا نحو مغانم زائفة سرعان ما سوف تتبدد. لقد دفع أعضاء الأخوان ثمن باهظ من دمائهم من اجل أن تصبح جماعتهم فصيل سياسي مقبول مجتمعيا و غير محظور. أراهم اليوم يبددون في الثورة كما بددوا في دماء شبابهم.

 بئس عاقبة الظالمين انفسهم.

04/9/11

عجز التفكير فى أحداث التحرير فى ليلة تسعة أبريل

.اشعر و يشعر كثيرون أن هناك شئ مثير للريبة فى الأحداث مؤلمة التى جرت ليلة تسعة أبريل

تساؤلات كثيرة تتصارع فى زهنى:

  1. كان المجلس العسكرى على دراية بأن هناك بعض الظباط ينوون الإعتصام فى التحرير، لماذا لم يتحرك؟ كان من الممكن التعامل مع الضباط الثائرين من داخل المؤسسة العسكرية أو على اقل التقدير على مداخل الميدان !!
  2. أغلب من كانوا فى التحرير كان سبب تواجدهم هو محاكمة مبارك و لكن تحول المشهد لمظاهرة فى الدفاع عن الضباط المعتصمين!!!
  3. لماذا طل علينا بعض “السلفيون” يحملون يافطات باللغة الإنجليزية مطالبين بالإفراج عن الشيخ عمر عبد الرحمن المسجون بالولايات المتحدة، و كأن هذا مطلب رئيسى للثورة؟
  4. فض إعتصام الضباط الثائرون كان متوقعاً، إذا لا تقبل أى مؤسسة عسكرية الإختلاف فى صفوفها و لكن: هل كان كل هذا العنف و التدمير و الإصابات و القتل ضرورى؟
  5. كان هناك تشتبت كبير بالأحداث الجارية فى غزة و كان البعض ملح فى طلب الجيش فى التدخل العسكرى فى هذا الشأن!!!

كل هذة التسؤلات و أكثر منهنا تبحث عن إجابة و لكن الشئ الوحيد الواضح هو وجوب التعامل الفورى مع الفاسدين و اولهم مبارك ثم أعوانه و تقديمهم إلى محاكمة عادلة بلا تباطؤ أو إستهانة بإرادة الشعب. البديل هو أنفراط عقد هذا الوطن و الفوضى.